Алгоритм Эдмондса Лекция 11. Идея алгоритма Эдмондса Пусть есть некоторое паросочетание M, построим M-чередующийся лес F. Начинаем с множества S вершин. - презентация

1 Алгоритм Эдмондса Лекция 11

2 Идея алгоритма Эдмондса Пусть есть некоторое паросочетание M, построим M-чередующийся лес F. Начинаем с множества S вершин не покрытых M и с пустого множества ребер. На каждом шаге алгоритм рассматривает вершину y соседнюю с внешней вершиной x. Пусть P(x) обозначает путь в F от x к корню. Возможны три случая и, соответственно, три операции (прирост, увеличение, истягивание).

3 Прирост y V(F) Тогда лес может быть наращен добавлением ребра {x, y} и ребра из M покрывающего y.

4 Увеличение y внешняя вершина в другой связной компоненте F. Тогда увеличим M вдоль P(x) U {x, y} U P(y).

5 Стягивание y внешняя вершина в той же связной компоненте F (с корнем q). Пусть r будет первой вершиной в P(x) (считая от x), которая принадлежит и P(y). Если r не корень, то она должна иметь степень не меньше 3. Следовательно r внешняя вершина. Тогда C := P(x) [x,r] U {x, y} U P(y) [y,r] цветок с не менее чем тремя вершинами. Стягиваем C.

6 Три случая Прирост: x 1, y 1 ; Увеличение: x 2, y 2 ; Стягивание 3: x 3, y 3. x1x1 y1y1 x2x2 y2y2 x3x3 y3y3 Цветок v w P(vw) увеличивающий путь

7 Максимальное паросочетание Если ни один из трех случаев не возник, то все соседи внешних вершин внутренние. Докажем, что тогда M максимально.

8 Доказательство Пусть X множество внутренних вершин, s:=|X|, и пусть t число внешних вершин. G – X имеет t нечетных компонент (каждая внешняя вершина изолирована в G – X ), то есть q G (X) – |X|= t – s. Из формулы Бержа-Татта получаем, что любое паросочетание оставляет по крайней мере t – s вершин непокрытыми. С другой стороны, число непокрытых вершин в M равно числу корней F и равно t – s по Утверждению Следовательно, M максимально.

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

10 Цветочный лес Определение 11.1 Дан граф G и паросочетание M в G. Подграф F из G называется цветочным лесом (относительно M), если существует разбиение V(F) = V 1 U V 2 U... U V k множества вершин, такое что F i := F[V i ] является максимальным фактор- критическим подграфом F с |ME(F i )| = (|V i | – 1)/2 (i = 1,...,k) и после стягивания каждого из V 1,...,V k получается чередующийся лес F'.

11 Цветки Определение 11.1 (продолжение) F i называется внешним цветком (внутренним цветком) если V i внешняя (внутренняя) вершина в F'. Все вершины внутреннего (внешнего) цветка называются внутренними (внешними). Цветочный лес в котором каждый внутренний цветок является простой вершиной называется специальным цветочным лесом. Все вершины G, не принадлежащие специальному цветочному лесу называются вне-лесными.

12 Специальный цветочный лес Паросочетание, внутренние вершины Нетривиальные внешние цветки

13 Замечание В дальнейшем, мы будем рассматривать только специальный цветочный лес. Лемма о стягивании цветков (Лемма 10.7) применима только к внешним цветкам. Лемма 10.7 Пусть G граф и M паросочетание в G, и C цветок в G (относительно M). Предположим, что существует M-чередующийся v- r-путь Q четной длины из вершины v, непокрытой M, в базу r цветка C, и E(Q) E(C) =. Пусть G и M получаются из G и M стягиванием V(C) к одной вершине. Тогда M максимально в G тогда и только тогда, когда M является максимальным паросочетанием в G.

14 Структура хранения специального цветочного леса для если непокрытых или база цветка в и внутренняя вершина в соответствии с чередующейся декомпозицией цветка содержащего x, если x внешняя вершина не является внешней вершиной является внешней вершиной и y база внешнего цветка в, содержащего

15 Специальный цветочный лес Паросочетание, внутренние вершины Нетривиальные внешние цветки u v ( (u) = v )

16 Максимальный путь Для каждой внешней вершины v определим P(v) как максимальный путь, заданный подпоследовательностью v, (v), ( (v)), ( ( (v))), ( ( ( (v)))),... Утверждение 11.2 Пусть F специальный цветочный лес относительно M, и пусть, : V(G) V(G) удовлетворяют (1) и (2). Тогда: a)Для каждой внешней вершины v, P(v) чередующийся v-q-путь, где q корень дерева F, содержащего v. b)Вершина x является внешней тогда и только тогда, когда либо (x) = x или ( (x)) (x) внутренней тогда и только тогда, когда ( (x)) = (x) и (x) x вне-лесной тогда и только тогда, когда (x) x и (x) = x и ( (x)) = (x).

17 Доказательство a) Из определения и леммы 10.5 начало последовательности v, (v), ( (v)), ( ( (v))), ( ( ( (v)))),... это M-чередующийся x-r-путь четной длины к базе цветка r. Если r не корень, то он покрыт M. последовательность продолжится ребрами {r, (r)} и { (r), ( (r))} ( (r)-внутренняя) ( (r)) внешняя вершина (можно применить индукцию).

18 Алгоритм Эдмондса Input: Граф G. Output: Максимальное паросочетание в G, заданное ребрами {x, (x)}. 1.Set μ(v):=v, φ(v):=v, ρ(v):=v и scanned(v):= false для всех v V(G). 2.If все внешние вершины просмотрены then stop, else пусть x внешняя вершина с scanned(x) = false. 3. Пусть y сосед x, такой что ( y вне-лесная ) или ( y внешняя и ρ(y) ρ(x)). If таких вершин нет then set scanned(x):= true и go to 2.

19 Прирост x y 4. If y вне-лесная, then set φ(y):=x и go to 3.

20 Увеличение 5.If P(x) и P(y) не имеют общих вершин then μ(φ(v)):=v, μ(v):=φ(v), для всех v P(x) с нечетным расстоянием от x и всех v P(y) с нечетным расстоянием от y; μ(x):=y; μ(y):=x; φ(v):=v, ρ(v):=v, scanned(v):= false для всех v V(G) Go to 2.

21 Увеличение x y w P(vw) увеличивающий путь v

22 Стягивание 6. Пусть r первая вершина из P(x)P(y), для которой ρ(r) = r. c нечетным расстоянием отна

23 Стягивание Паросочетание, внутренние вершины Нетривиальные внешние цветки (u, v) | (u) = v x y r q w (w) = w (w) = q (q) = w (q) = r

24 Алгоритм Эдмондса Лемма 11.3 Следующие утверждения выполняются на любом шаге Алгоритма Эдмондса : a)Ребра {x, (x)} принадлежат M; b)Ребра {x, (x)} и {x, (x)} образует специальный цветочный лес F относительно M (+ некоторые изолированные ребра паросочетания); c)Свойства (1), (2) и (3) выполнены относительно F. Структура хранения специального цветочного леса не нарушена.

25 b) Ребра {x, (x)} и {x, (x)} образует специальный цветочный лес F относительно M (+ некоторые изолированные ребра паросочетания); На шаге 1 и после шага 5 («увеличение») получаем специальный цветочный лес без ребер. Шаг 4 («прирост») корректно увеличивает специальный цветочный лес на два ребра. На шаге 6 r либо корень, либо имеет степень по крайней мере 3 r внешняя. Пусть B:= V(P(x) [x,r] ) U V(P(y) [y,r] ). Рассмотрим ребро {u,v}, u B и v B. Так как F(B) содержит почти совершенное паросочетание, то {u,v} M тогда и только тогда {u,v} = {r, (r)}. Более того u была внешней до выполнения шага 6 v внутренняя до выполнения шага 6. F остается специальным цветочным лесом после шага 6.

26 с) Структура хранения специального цветочного леса Покажем, что после шага 6 и соответствуют M-чередующейся декомпозиции нового цветка. Пусть x и у две внешние вершины некоторой связной компоненты специального цветочного леса и r первая вершина из P(x)P(y), для которой ρ(r) = r. Новый цветок B:= {v V(G): ρ(v) P(x) [x,r] U P(y) [y,r] } (v) не изменяется для v B с ρ(v) = r. Пусть B old := {v V(G): ρ(v) = r}, (v) задает декомпозицию B old. Следующее ушко будет P(x) [x,x] U {x,y} U P(y) [y,y], где x и y первые вершины на P(x) и P(y) в B old. Каждое ушко Q старого внешнего цветка B' B, Q \ (P(x) U P(y)) является ушком в новой M-чередующейся декомпозиции.

27 Алгоритм Эдмондса Теорема 11.4 (Edmonds [1965]) Алгоритм Эдмондса находит максимальное паросочетание за время O(n 3 ), где n = |V(G)|.

28 Доказательство корректности Лемма 11.3 и Утверждение 11.2 на каждом шаге мы корректно определяем функции, корректно определяем паросочетание M. Пусть M и F паросочетание и специальный цветочный лес, полученные в момент остановки алгоритма. Пусть X множество внутренних вершин и B множество баз внешних цветков в F. |V(G)| – |2M| = |B| – |X|

29 Доказательство корректности Шаг 3 любая вершина y соседняя с произвольной внешней вершиной x, либо внутренняя либо принадлежит тому же цветку что и x. внешний цветок в F является нечетной компонентой в G – X. любое паросочетание должно оставить |B| – |X| вершин непокрытыми. M максимальное паросочетание.

30 Время работы Утверждение 11.2 статус каждой вершины можно проверить за константное время. Шаг 4 выполняется за одну элементарную операцию и шаги 5 и 6 требуют O(n) элементарных операций. Между двумя увеличениями шаги 4 и 6 выполняются не более n раз каждый. Между двумя увеличениями каждая вершина просматривается только один раз и шаг 3 для каждой вершины требует O(n) элементарных операций. Общее время работы между двумя увеличениями не превосходит O(n 2 ) элементарных операций. Общее время работы алгоритма O(n 3 ) элементарных операций.

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

32 Упражнение 11.2 Показать, что любой граф на n вершинах, у которого степень каждой вершины не меньше k, имеет паросочетание мощности min{k, n/2}.

33 Упражнение 11.3 Пусть G двудольный граф с биразбиением V(G) = A U B. Предположим, что S A, T B и существует паросочетание, покрывающее S, и паросочетание, покрывающее T. Доказать, что существует паросочетание, покрывающее SUT.

34 Упражнение 11.4 Доказать, что любой связный 3-регулярный граф с не более чем двумя мостами имеет совершенное паросочетание. Привести пример связного 3-регулярного графа, который не имеет совершенного паросочетания.

35 Упражнение 11.5 Можно ли найти в произвольном графе реберное покрытие минимальной мощности в полиномиальное время.