M-чередующаяся декомпозиция Лекция 10. Нечетная декомпозиция Теорема 9.7 (Lovász [1972] ) Граф является фактор-критическим тогда и только тогда, когда. - презентация

1 M-чередующаяся декомпозиция Лекция 10

2 Нечетная декомпозиция Теорема 9.7 (Lovász [1972] ) Граф является фактор-критическим тогда и только тогда, когда он имеет нечетную декомпозицию. Более того, начальная вершина в декомпозиции может быть выбрана произвольна.

3 M-чередующаяся декомпозиция Определение 10.1 Даны фактор-критический граф G и почти совершенное паросочетание M, M-чередующейся декомпозицией графа G называется нечетная декомпозиция, такая что каждое ушко является M-чередующимся путем. Следствие 10.2 (из доказательства теоремы 10.17) Для любого фактор-критического графа G и любого почти совершенного паросочетания M в G существует M-чередующаяся декомпозиция.

4 Эффективный способ хранения информации о M-чередующейся декомпозиции Определение 10.3 (Lovazs & Plammer 1986) Пусть G фактор-критический граф и M почти совершенное паросочетание в G. Пусть r, P 1,..., P k чередующаяся декомпозиция и, : V(G) V(G) две функции. Будем говорить, что и соответствуют декомпозиции r, P 1,..., P k, если (x) = y, если {x, y} M (x) = y, если {x, y} E(P i )\ M и x {r}UV(P 1 )U... UV(P i–1 ), (r) = (r) = r.

5 и P1P1 P2P2 P3P3 r M, E(P i )\ M x v w (x) = v (x) = w h (w) = h (h) = w

6 Алгоритм построения M-чередующейся декомпозиции Input: фактор-критический граф G, функции,, соответствующие M-чередующейся декомпозиции. Output: M-чередующаяся декомпозиция r, P 1,...,P k. 1.Set X := {r}, где r: (r) = r ; k := 0 и стек (для ушек) пустой. 2.If X = V(G) then go to 5. If стек непустой then пусть v V(G )\ X граничная точка последнего элемента стека else выбрать произвольную v V(G )\ X. 3.Set x:= v, y:= (v) и P:=({x,y},{{x,y}}). While ( (x)) = x do: set P:=P+{x, (x)}+{ (x), ( (x))} и x:= ( (x)). While ( (y)) = y do: set P:=P+{y, (y)}+{ (y), ( (y))} и y:= ( (y)). Set P:=P+{x, (x)}+{y, (y)}. (Pушко с y как внутренней вершиной). Положить P в конец стека.

7 Алгоритм построения M-чередующейся декомпозиции 4. While обе граничные точки последнего элемента P в стеке лежат в X do: Удалить P из стека, set k:=k+1, P k :=P и X:=X U V(P). Go to For всех {y,z} E(G)\(E(P 1 ) U…U E ( P k )) do: Set k:=k+1 и P k :=({y, z},{{y, z}}).

8 Пример работы алгоритма P1P1 P2P2 P3P3 r M, E(P i )\ M Set x:= v, y:= (v) и P:=({x,y},{{x,y}}) While ( (x)) = x do: set P:=P+{x, (x)}+{ (x), ( (x))} и x:= ( (x)). While ( (y)) = y do: set P:=P+{y, (y)}+{ (y), ( (y))} и y:= ( (y)). Set P:=P+{x, (x)}+{y, (y)}

9 Свойство алгоритма Утверждение 10.4 Пусть G фактор-критический граф и, функции, соответствующие M-чередующейся декомпозиции. Тогда эта декомпозиция единственна с точностью до порядка ушек. Алгоритм построения M-чередующейся декомпозиции корректно определяет список ушек за линейное время.

10 Функции, Лемма 10.5 Пусть G фактор-критический граф и, функции, соответствующие M-чередующейся декомпозиции. Пусть r вершина, не покрытая M. Тогда максимальный путь, заданный последовательностью x, (x), ( (x)), ( ( (x))), ( ( ( (x)))),..., определяет M-чередующийся x-r-путь четной длины для всех x V(G)\{r}.

11 Доказательство Пусть x V(G)\{r} и пусть будет первое ушко, которое содержит x. Тогда начало последовательности (x, (x), ( (x)), ( ( (x))), ( ( ( (x)))),...) это путь Q P из x в y, где y {r} U V(P 1 ) U... U V(P i–1 ). Так как, соответствуют M-чередующейся декомпозиции, то последнее ребро Q не принадлежит M. Если y = r, то получаем x-r-путь четной длины, иначе применяем индукцию по i.

12 Контрпример Утверждение обратное Лемме 10.5 не верно: На рисунке и также определяют чередующиеся пути к вершине, непокрытой паросочетанием. Однако, и не соответствует никакой M-чередующейся декомпозиции. Синие ребра ребра в паросочетании, дуги из u в v указывает на (u) = v.

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

14 Увеличивающие пути в произвольных графах v1v1 v2v2 v7v7 v6v6 v3v3 v8v8 v4v4 v5v5 Чередующаяся реберная прогрессия v 1, v 2, v 3, v 4, v 5, v 6, v 7, v 5, v 4, v 8, которая не является путем, так как проходит через нечетный цикл v 5, v 6, v 7. Заметим, что в этом примере существует увеличивающий путь v 1, v 2, v 3, v 7, v 6, v 5, v 4, v 8, но не ясно как его найти.

15 Нечетные циклы Что делать, если мы наткнулись на нечетный цикл? Оказывается достаточно стянуть его в вершину. В графе со стянутом циклом существует совершенное паросочетание тогда и только тогда, когда оно существует в исходном графе.

16 Цветки Определение 10.6 Пусть G граф и M паросочетание в G. Цветком в G относительно M называется фактор-критический подграф C G с |M E(C)|=(|V(C)| – 1)/2. Вершина C непокрытая M E(C) называется базой C.

17 Стягивание Пусть задан граф G и X V(G). Стягиванием X называется следующая процедура: удалим все ребра внутри множества X, заменим все вершины X на новую вершину x и все ребра вида {v, w} с v X и w X на ребра {x, w} (возможно возникновение параллельных).

18 Цветки и стягивание v1v1 v2v2 v7v7 v6v6 v3v3 v8v8 v4v4 v5v5 v1v1 v2v2 v7v7 v3v3 v8v8 v new

19 Лемма о стягивании цветков Лемма 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.

20 Доказательство Предположим, что M не является максимальным паросочетанием в G. Рассмотрим N=MQ. | N | = | M | N не является максимальным паросочетанием в G. Теорема Берга N-увеличивающий путь P [x 1,x 2 ] в G. Так как M покрывает r, то N не покрывает r. v r M Q v r N Q

21 Доказательство Либо x 1 С, либо x 2 С, пусть x = x 1. Если P и С не пересекаются, пусть y = x 2. Иначе, пусть y будет ближайшая к x вершина в P, которая принадлежит С. Пусть P ' получается из P [x,y] стягиванием цветка V(С) в G. N ' не покрывает крайние точки P '. P ' является N ' -увеличивающим путем в G. Теорема Берга N ' не максимальное паросочетание в G. | N' | = | M' | M ' не максимальное паросочетание в G.

22 Доказательство Предположим, что M ' не является максимальным паросочетанием в G '. Пусть N ' паросочетание в G ', такое что | N' | > | M' |. N ' соответствует некоторому паросочетанию N 0 в G, которое покрывает не более одной вершины в C. Так как C фактор-критический, к N 0 можно добавить k = (|V(C)| – 1)/2 ребер до паросочетания N в G. | N | = | N 0 | + k = | N' | + k > | M' | + k = | M | M не максимальное паросочетание в G.

23 Неправильное стягивание v1v1 v2v2 v7v7 v6v6 v3v3 v8v8 v4v4 v5v5 v new v8v8 v5v5 v1v1

24 Чередующийся лес Определение 10.8 Даны граф G и паросочетание M в G. Чередующимся лесом относительно M в G называется лес F в G со следующими свойствами: a) V(F) содержит все вершины непокрытые M. Каждая связная компонента F содержит только одну вершину непокрытую M, ее корень. b) Вершина v V(F) на четном расстоянии от корня называется внешней, вершина v V(F) на нечетном расстоянии от корня называется внутренней (корень является внешней вершиной.) Все внутренние вершины имеют степень 2 в F. c) Для любой v V(F), путь из v к ее корню является M-чередующимся.

25 Чередующийся лес (2) Паросочетание и внутренние вершины. Внешние вершины.

26 Внешние и Внутренние Вершины Утверждение 10.9 В любом чередующемся лесе число внешних вершин отличных от корня равно числу внутренних вершин.