2 Определения .9.3. Паросочетание графа

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

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

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

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

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

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

Очевидно:

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

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

Меры

• (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, присваивается единичная емкость, а для всех остальных дуг емкость принимается равной бесконечности.

Пример

L

R

●

●

●

●

●

L

R

s

t

емк.=∞

●

●

●

●

●

емк.=1

емк.=1

Рис.2.9.3. Приведение двудольного графа сети

Теорема

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

Алгоритм

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

Дополняющие пути

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

Пусть P= v₀, v₁, v₂, …, v_k будет простым М-чередующимся путем. Р будет М-дополняющим путем, если v₀ и v_k не являются вершинами в паросочетании (они являются М-свободными).

Пример

v_k-1

М-свободная вершина

v₀

v₁

v_k

М-свободная вершина

Рис.2.9.4. М-дополняющий путь

Теорема существования

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

Алгоритмы

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

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

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

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

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

Пример

12

 11

12

 11

1

 6

1

 6

2

 7

2

 7

3

 8

3

 8

4

 9

4

 9

5

 10

5

 10

Наибольшее паросочетание

{{1,11},{3,10},{4,8}, {5,6}}

Рис.2.9.5. Наибольшее паросочетание, найденное алгоритмом Хоплкофта-Карпа

2.9.4. Вершинное покрытие

Определения

Вершинным покрытием S графа G=(V,E) является подмножеством вершин V, которое инцидентно ко всем ребрам негорафа, т.е. для каждого ребра {u,v}E для uS или vS.

Минимальным вершинным покрытием графа G=(V,E) называется вершинное покрытие минимальной мощности S`.

Пример

v₂



v₁



Вершинное покрытие

и минимальное вершинное покрытие

S`={v₁, v₄}



v₃



v₄

Рис.2.9.4. Вершинное покрытие

Меры

• (G) – число вершинного покрытия графа. Является числом вершин минимального вершинного покрытия этого графа.

Класс сложности

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

Точное решение

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

Жадный алгоритм

И

Алгоритм G1

меется большое число жадных алгоритмов для вычисления «приблизительно» минимального вершинного покрытия. Среди них есть два алгоритма, дающих наилучшее приближение к оптимуму.

1. Начальное значение множества вершинного покрытия S:=0;

2. Выбрать любое ребро {u,v};

3. S:=S  {u,v};

4. Удалить вершины u и v, а также все инцидентные к ним ребра и все изолированные вершины.

5. Повторить 2 до тех пор, пока в графе есть ребра.

С

Пример

ложность этого алгоритма – O(n+m), где n –число вершин и m – число ребер графа.

e



c



b



Начальное значение

S:=0



a



d



f



g

Шаг 1. Выбираем ребро {e,d};

S:={e,d};

c



b



Удаляем вершины e и d и все инцидентные к ним ребра и изолированные вершины. Получаем подграф



a

Шаг 2. Выбираем ребро {b,c};

S:={b,c,d,e};

Удаляем все инцидентные ребра и изолированные вершины. Подграф пуст – алгоритм стоп.

Полученное вершинное покрытие неминимально. Минимальным покрытием будет S`={b,d,e}.

Алгоритм G1

1. Вычислить максимальное или даже наибольшее паросочетание М графа G.

2. Взять вершины максимального или наибольшего паросочетания в качестве вершинного покрытия графа G.

Замечание

Аппроксимационное отношение алгоритмов G₁и G₂ равно 2.

2.9.5. Реберное покрытие

Определения

Реберным покрытием называется подмножество ребер U` графа G=(V,E), U`E, такое, что всякая вершина графа G инцидентна ребру из U`.

Минимальное реберное покрытие- минимальное среди всех возможных подмножеств реберных покрытий.

Пример

Рис.2.9.7. Реберное покрытие

Меры

• (G) – число реберного покрытия. Равно размеру |U`| минимального реберного покрытия.

Класс сложности

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

2.9.6. Теоремы о подструктурах графа

Теорема 1 (Идентичности Галлаи-Gallai Idtntities)

Пусть для любого графа G=(V,E) будут

n=|V|,

(G) – число независимости,

(G) – число реберного покрытия,

(G)– число вершинного покрытия,

(G) – число паросочетания,

тогда

• (G) + (G) =n

• (G) + (G) =n, если граф G не имеет изолированных вершин.

Теорема 2

Справедливы следующие утверждения:

1. Минимальное реберное покрытие будет минимальным тогда и только тогда, когда оно содержит наибольшее паросочетание.

2. Максимальное паросочетание является наименьшим тогда и только тогда, когда оно содержится в минимальном реберном покрытии.

Теорема 3

Для любого графа G=(V,E) справедливо следующее неравенство

(G)  (G)  2(G).

Теорема 3 (Konig`s Minimax Theorem)

Если G=(V,E) является двудольным графом, то

(G)  (G).

7. Доминирующее множество вершин

Определения

Доминирующим множеством (вершин) графа G=(V,E) является подмножество V’ V такое, что любая вершина, не находящаяся в V', соединяется по крайней мере одним ребром в вершинами из V’.

Меры

γ(G) –доминантное число графа .Является числом вершин самого меньшего доминирующего множества графа.

Класс сложности

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

Замечания

Доминирующие множества тесно связаны с независимыми множествами: максимальное независимое множество в графе необходимо является доминирующим множеством. Однако, доминирующее множество может и не быть независимым.

Если S – связное доминирующее множество, то можно сформировать каркасное дерево графа G, в котором S формирует множество вершин дерева, не принадлежащим листьям (степени 1). Если T – каркасное дерево графа с тремя и более вершинами, то не листовые вершины дерева T формируют связное доминирующее множество. Таким образом, нахождение минимального связного доминирующего множества эквивалентно нахождению каркасного дерева с максимально возможным числом листьев.