Лекция: Независимое множество вершин
| |||
Независимое множество вершин 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), однако это будет не во всех случаях, т.к. алгоритм – жадный.
2.9.3. Паросочетание графаОпределения
Паросочетанием 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 – число вершин графа).
| ||||||
|