Паросочетания в двудольных графах Лекция 8

Паросочетание Паросочетанием в графе G называется множество попарно несмежных ребер.

Задача «Максимальное Паросочетание» Дан граф G. Найти паросочетание в G максимальной мощности.

Совершенное паросочетание Определение 8.1. Пусть G граф и M паросочетание в G. Будем говорить, что вершина v покрыта M, если v e для некоторого e M. M называется совершенным паросочетанием, если все вершины покрыты M.

Биразбиение Биразбиением графа G называется разбиение множества вершин на два подмножества, V(G)=A B, такое что подграфы индуцированные на A и B оба пустые. Граф называется двудольным, если он имеет биразбиение.

Паросочетание в двудольном графе Для графа G, пусть (G) обозначает мощность максимального паросочетания, а (G) мощность минимального вершинного покрытия в G. Теорема 8.2 (König [1931]) Если G двудольный, то (G) = (G).

Доказательство G' = (V(G) {s,t}, E(G) {{s,a}: a A} {{b,t}: b B}) (G) – максимальное число вершинно-непересекающихся s-t-путей. (G) – минимальное число вершин удаление которых разделяет вершины s и t.

Вторая Теорема Менгера Theorem 7.2 (Menger [1927] ) Пусть G граф (ориентированный или неориентированный), пусть s и t две несмежные вершины и k N. Тогда существует k вершинно- непересекающихся s-t-путей, тогда и только тогда, когда после удаления любых k – 1 вершин (отличных от s и t) t остается достижима из s.

Доказательство G' = (V(G) {s,t}, E(G) {{s,a}: a A} {{b,t}: b B}) (G) – максимальное число вершинно-непересекающихся s-t-путей. (G) – минимальное число вершин удаление которых разделяет вершины s и t. 2-я теорема Менгера (G) = (G).

Теорема Холла Теорема 8.3 (Hall [1935] ) Пусть G двудольный граф с биразбиением V(G) = A B. Тогда G имеет паросочетание, покрывающее A, тогда и только тогда, когда | (X)| |X| для всех X A. ( (X) – множество вершин соседних с X.)

Доказательство (достаточность) Пусть G не имеет паросочетание, покрывающее A ( (G) < |A|). Теорема 8.2 (G) < |A|. Рассмотрим A' A и B' B, такие что A' B' покрывают все ребра и | A' B' | < | A |. Тогда (A /A' ) B'. | (A /A' ) | |B'| < | A | – | A' | = |A /A' |, что противоречит условию теоремы.

Теорема о бракосочетаниях Теорема 8.4 (Frobenius [1917] ) Пусть G двудольный граф с биразбиением V(G) = A B. Тогда G имеет совершенное паросочетание, тогда и только тогда, когда |A| = |B| и | (X)| |X| для всех X A.

Паросочетание в двудольном графе Теорема 8.5 Задача «Максимальное Паросочетание» в двудольном графе G может быть решена за время O(nm), где n = |V(G)| и m = |E(G)|.

Справка Используя идею о кратчайшем увеличивающем пути можно получить алгоритм с трудоемкостью O(n 0.5 (m + n)) (Hopcroft & Karp 1973).

M- увеличивающий путь Определение 8.6 Пусть G граф, и M паросочетание в G. Путь P называется M-чередующимся путем, если E(P) \ M является паросочетанием. Чередующийся путь называется M-увеличивающим, если его граничные точки не покрываются M, то есть | E(P) \ M | > | E(P) M |.

Пример M-увеличивающего пути M P:P: E(P)\ M

Паросочетание и увеличивающий путь Theorem 8.7 (Berge [1957] ) Пусть G граф, и M паросочетание в G. Тогда M является максимальным тогда и только тогда, когда не существует M-увеличивающего пути.

Доказательство Если M-увеличивающий путь P существует, то симметрическая разность ME(P) будет паросочетанием большей мощности. Если существует паросочетание | M '| > | M |, то MM ' является вершинно- непересекающимся объединением путей и циклов, один из которых является увелличивающим.

Алгебраический подход Пусть G простой граф и пусть G' орграф, полученный из G произвольной ориентацией ребер. Для произвольного вектора x определим матрицу Татта.

Матрица Татта

Паросочетание и матрица Татта Теорема 8.8 (Tutte [1947] ) Граф G имеет совершенное паросочетание тогда и только тогда, когда det T G (x) 0.

Доказательство V(G) = {v 1,…,v n } Пусть S n множество всех перестановок {1,…, n}. Каждая перестановка π S' n соответствует орграфу H π = ( V(G),{(v i,v π(i) ): i = 1,…, n}), где ровно одна дуга входит в каждую вершину и ровно одна дуга выходит из нее. (H π Ğ').

Пример H π MHπHπ vivi vjvj π(i)=j, π(j)=i.

Доказательство Если существует перестановка π S' n такая что H π состоит только из четных циклов, то в G есть совершенное паросочетание. Пусть это не так. То есть для каждой π S' n существует нечетный цикл. Тогда r( π ) S' n такая, что H r( π ) получается из H π обратной ориентацией дуг в первом нечетном цикле (r(r( π )) = π).

vivi vjvj π(i)=j, π(j)=k, π(k)=i. vkvk vivi vjvj π(i)=k, π(j)=i, π(k)=j. vkvk HπHπ Hr(π)Hr(π) Пример H π и H r(π)

sgn(π)= sgn(r(π)) w1w1 w2w2 w 2k+1 HπHπ Hr(π)Hr(π) w1w1 w2w2 w 1,w 2,w 3, …, w 2k,w 2k+1 w 2,w 3,w 4, …, w 2k+1,w 1 w 1, w 2,w 3, …, w 2k,w 2k+1 w 2k+1,w 1,w 2, …, w 2k-1,w 2k Одна перестановка получается из другой за 2к транспозиций.

Доказательство Следовательно, два соответствующих этим перестановкам слагаемые в сумме взаимно сокращаются. Так как это выполняется для всех пар π и r(π), то det T G (x)0.

Вероятностный Алгоритм Следствие 8.9 (Lovász [1979] ) Пусть x = (x e ) e E(G) случайный вектор, каждая координата которого равномерно распределена в [0,1]. Тогда с вероятностью 1 ранг T G (x) в точности равен 2 (G).

Упражнение 8.1 Пусть G произвольный граф, M 1 и M 2 два максимальных паросочетания в нем. Доказать, что | M 1 | | M 2 |.

Упражнение 8.2 Доказать, что k-регулярный двудольный граф имеет k попарно не пересекающихся совершенных паросочетаний.