Лекция: Независимое множество вершин

Независимое множество вершин S есть такое подмножество вершин графа G, что любые две вершины в нем не смежны (никакая пара вершин не соединена ребром).

Среди всех возможных независимых множеств Si выделяют наибольшее – максимальное независимое множество вершин.

· a(G) – число независимости, определяемое числом вершин максимального независимого множества вершин.

Проблема нахождения независимого множества вершин является NP-полной, а проблема нахождения максимального независимого множества вершин – NP-тяжелой.

Как и в случае проблемы нахождения максимальной клики существуют точные алгоритмы решения, однако они имеют экспоненциальную сложность. Точные решения удается получить для графов с числом вершин менее 500.

Относятся к тем же группам, что и для проблемы нахождения максимальной клики.

Введем следующее обозначение:

Si – независимое множество вершин графа G=(V,E).

1. Начальное условие Si:=0;

2. Если граф не пустой, то случайны образом выбираем вершину vi с наименьшей степенью;

3. Si:= Si È vi ;

4. Удалить вершину vi и все инцидентные к ней вершины. Перейти к п.2.

Шаг 1. Определяем степени вершин: deg1=3; deg2=3; deg3=3; deg4=3; deg5=3; deg6=5; deg7=2; deg8=2.

Имеется две вершины (7 и8) с одинаковой минимальной степенью. Выбираем вершину 8.

Si:={8}

Удаляем вершину 8 и все инцидентные ей вершины (вершины 1 и 6). Получаем подграф

Шаг 2. Определяем степени вершин подграфа, полученного на предыдущем шаге: deg2=1; deg3=3; deg4=3; deg5=2; deg7=1.

Имеется две вершины минимальной степени – вершины 2 и 7. Выбираем вершину 2.

Si:={2,8}

Удаляем вершину 2 и инцидентную ей вершину 3. Получаем подграф

Шаг 3. Определяем степени вершин подграфа, полученного на предыдущем шаге: deg4=3; deg5=2; deg7=1.

Вершина 7 имеет наименьшую степень.

Si:={2,7,8}

Удаляем вершину 7 и инцидентную ей вершину 4. Получаем подграф, состоящий из одной вершины 5.

Si:={2,5,7,8}

Граф пустой, алгоритм стоп.

Полученное множество независимых вершин совпало с максимальным (см.рис.2.9.2), однако это будет не во всех случаях, т.к. алгоритм – жадный.

Паросочетанием M графа G=(V,E) является такое подмножество ребер E, что никакие два ребра в М не инцидентны любой вершине vÎV (иными словами, в М нет двух ребер, имеющих общую вершину).

Вершина vÎV будет М-покрытой, если она инцидентна ребру в М, в противном случае вершина будет М-непокрытой.

Паросочетание М граф G будет совершенным, если все вершины графа будут М-покрыты.

Среди всех возможных паросочетаний графа выделяют два особых вида:

· максимальное (maximal) паросочетаное — паросчетание М в граф, не содержащееся ни в одном другом паросочетании;

· наибольшее сочетание — паросочетание наибольшего размера среди всех паросочетаний графа G.

Очевидно:

1. в графе могут быть несколько паросочетаний одного наибольшего размера;

2. максимальное паросочетание ¹ наибольшее паросочетание.

· n(G) – число паросочетаний, определяемое числом ребер наибольшего паросочетания графа.

· def(G) – дефецит графа — задаваемое числом М-непокрытых вершин графа (если паросочетание является совершенным, то def(G)=0).

Нахождение паросочетания графа относится к NP-полному классу, а проблема определения наибольшего паросочетания – NP-тяжелая.

Точное решение проблемы нахождения наибольшего паросочетания известно (например, используется метод целочисленного линейного программирования), однако время решения проблемы растет экспоненциально с ростом размерности графа.

Наиболее разработанное направление – паросочетания для двудольных графов.

Ниже рассматриваются два подхода:

· сведение к задаче определения максимального потока в сети;

· метод, основанный на поиске дополняющих путей в графе.

Известно приведение проблемы нахождения числа паросочетаний двудольного графа к проблеме нахождения максимального потока в сети, а последняя проблема решается в полиномиальное время.

Это приведение достаточно простое. Для заданного двудольного графа G=(V,E) с двумя подмножествами вершин L и R, V=LÈR, строится сеть G`=(V`,E`):

1. к графу G=(V,E) добавляется две новые вершины стока и истока s и t, т.е. V`=VÈ{s,t}.

2. дуги (направленные линии) графа G` задаются следующим образом: E`={{s,u}:ÎL}È{{u,v}ÎE: uÎL,vÎR}È{{v,t}: vÎR}.

3. Всем дугам, инцидентным s и t, присваивается единичная емкость, а для всех остальных дуг емкость принимается равной бесконечности.

Значение наибольшего s-t потока в G` равно числу наибольшего паросочетания в G.

Наибольший s-t поток можно найти с помощью алгоритма Форда-Фалкерсона.

Путь P= v0, v1, v2, …, vk в графе G является М-чередующимся, если он содержит поочередно ребра из паросочетания М и ребра вне его (в E/М).

Пусть P= v0, v1, v2, …, vk будет простым М-чередующимся путем. Р будет М-дополняющим путем, если v0и vk не являются вершинами в паросочетании (они являются М-свободными).

М является наибольшим паросочетанием тогда и только тогда, когда по отношениюк М в графе нет М-дополняющих путей.

Эта теорема лежит в основании почти всех известных алгоритмов определения наибольшего паросочетания в произвольном графе. Основная идея этих алгоритмов:

· начав с заданного или нулевого паросочетания, попытаться найти М-дополняющий путь по отношению к данному паросочетанию.

· Использовать эти пути для увеличения паросочетания до тех пор, пока имееются М-дополняющие пути.

Заметим, что число графа с общем случае растет экспоненциально с ростом размера графа. Поэтому потребовались эффективные алгоритмы поиска дополняющих путей.

Для двудольных графов одним из самых эффективных и популярных алгоритмов поиска наибольшего паросочетания является алгоритм Хопкрофта-Карпа (Hopcroft-Karp), исполняемый за О(n4) (n – число вершин графа).