Декомпозиция Эдмондса-Галлаи

Определение:

[math]o(G-U)[/math] - количество компонент связности нечетного размера в [math] G[V-U][/math].

Теорема (Татта-Бержа):

дан граф [math]G[/math], размер максимального паросочетания в нем [math]v(G)[/math] равен: [math]v(G) = min(U in V)1/2(|V|-|U|-o(G-U)) [/math]

Определение:

множество U, на котором достигается минимум в формуле Татта-Баржа назовем множеством свидетелей.

Утверждение:

выполняется следующее: все вершины из U покрыты любим максимальным паросочетанием в G если K - множество вершин компоненты G-U, тогда любое максимальное паросочетание в G покрывает как минимум половину вершин в K. В частности, каждая вершина в четной компоненте покрыта любым максимальным паросочетанием.

Утверждение:

если U - не пустое множество свидетелей Татта-Бержа для графа G, тогда в G есть вершины, которые входят в любое максимальное паросочетание.

Определение:

граф G = (V, E) называется фактор-критическим, если в нем нем полного паросочетания, но для каждой вершины v из V граф G-v имеет полное.

Теорема:

граф G факторо-критический тогда и только тогда, когда для каждой вершины v из V существует максимальное паросочетание в G, которое не покрывает вершину v.

Утверждение:

пусть C - цикл нечетной длины в G. Если граф G/С, полученный сжатием C в одну вершину, фактор-критический, то и G - фактор-критический.

Структурная теорема Эдмондса-Галлаи

Определение:

необходимые определения: [math]D(G) = \{v \in V |[/math] существует максимальное паросочетание, не покрывающее [math] v\}[/math] [math]A(G) = N(D(G)) \setminus D(G)[/math] [math]C(G) = V \setminus( D(G) \bigcup A(G) )[/math] [math] \alpha (G) [/math] - размер максимального паросочетания в [math]G[/math]

Теорема (Галлаи):

[math]G[/math] - фактор-критический граф [math] \Leftrightarrow [/math] [math]G[/math] - связен и для любой вершины[math] u \in V(G) [/math] выполняется равенство [math] \alpha (G - u) = \alpha (G)[/math].

Лемма (Галлаи, о стабильности):

пусть [math] a \in A(G).[/math] Тогда: [math]D(G - a) = D(G)[/math] [math]A(G - a) = A(G) \setminus \{a\}[/math] [math]C(G - a) = C(G)[/math] [math] \alpha (G - a) = \alpha (G) - 1.[/math]

Доказательство:

[math]\triangleright[/math]

Достаточно доказать, что [math]D(G-a) = D(G)[/math]. [math]1)[/math] покажем, что [math]D(G - a) \supset D(G)[/math] : Пусть [math]u \in D(G)[/math]. Тогда существует максимальное паросочетание [math] Mu [/math] графа [math]G[/math], не покрывающее [math]u[/math]. Поскольку любое максимальное паросочетание графа [math]G[/math] покрывает a, то [math] \alpha (G - a) = \alpha (G) - 1 [/math] и более того, если [math] ax \in Mu [/math], то [math]Mu \setminus {ax} [/math] - максимальное паросочетание графа [math] G - a [/math], не покрывающее [math] u [/math]. Таким образом, [math]D(G - a) \supset D(G) [/math]. [math]2)[/math]покажем, что [math] D(G − a) \subset D(G)[/math]: Предположим, что существует максимальное паросочетание [math]M'[/math] графа[math] G - a[/math], не покрывающее вершину [math]v not \in D(G)[/math]. Пусть [math] w \in D(G) [/math]- смежная с[math] a \in A(G)[/math] вершина, а [math] Mw [/math]- максимальное паросочетание графа [math] G [/math], не покрывающее [math] w [/math]. Так как [math] v not \in D(G) [/math], максимальное паросочетание [math] Mw [/math] покрывает вершину [math]v[/math]. Рассмотрим граф [math] H = G(Mw \bigcup M') [/math] - очевидно, он является объединением нескольких путей и чётных циклов. Пусть [math] U [/math] - компонента связности графа [math] H [/math], содержащая [math]v[/math]. Так как [math] dH(v) = 1 [/math], то [math] P = H(U) [/math] - путь с началом в вершине [math]v[/math]. В пути [math]P[/math] чередуются рёбра из [math] Mw и M' [/math], причём начинается путь ребром из [math]Mw [/math] . Так как [math] dH(a) = 1 [/math], то вершина a либо не принадлежит пути [math]P[/math], либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию [math] Mw[/math]). Рассмотрим несколько случаев: a. Путь [math]P[/math] кончается ребром из [math] M'[/math] (см. рисунок) Рассмотрим паросочетание [math]Mv = Mw \oplus E(P)[/math] (симметрическая разность [math] Mw и E(P)[/math]. то есть, рёбра, входящие ровно в одно из двух множеств). Очевидно, [math]Mv[/math] - максимальное паросочетание графа [math] G[/math], не покрывающее [math] v[/math], поэтому [math] v \in D(G)[/math], противоречие. b. Путь [math]P[/math] кончается ребром из [math] Mw[/math], вершина a - конец пути [math]P[/math]. (см.рисунок) Рассмотрим паросочетание [math]Mv∗ = (Mw \oplus E(P)) \bigcup \{aw\} [/math]. Тогда [math] Mv∗ [/math] - максимальное паросочетание графа [math] G [/math], не покрывающее [math] v [/math], поэтому [math] v \in D(G) [/math], противоречие. c. Путь [math] P [/math] кончается ребром из [math] Mw, a \in V(P) [/math] (см. рисунок) Рассмотрим паросочетание [math] M'' = M \oplus E(P) [/math]. Тогда [math] |M''| = |M'| + 1 [/math], причём [math]M'' \subset E(G - a)[/math]. Противоречие с максимальностью паросочетания [math]M'[/math]. Таким образом, наше предположение невозможно и [math]D(G - a) \subset D(G)[/math]. А значит, [math]D(G - a) = D(G)[/math].

[math]\triangleleft[/math]

Теорема (Галлаи, Эдмондс):

Для графа [math] G = (V, E)[/math] выполняется: [math]1) U = A(G) [/math] - множество свидетелей Татта-Бержа [math]2) С(G) [/math] - объединение всех четных компонент [math]G - A(G)[/math] [math]3) D(G) [/math] - объединение всех нечетных компонент [math]G - A(G)[/math] [math]4)[/math] каждая компонента в [math] G - A(G)[/math] - фактор-критическая

Доказательство:

[math]\triangleright[/math]

1) Последовательно удаляя вершины множества[math] A = A(G)[/math], по лемме о стабильности мы получим: [math]D(G - A) = D(G),[/math] [math]A(G - A) = \O, [/math] [math]C(G - A) = C(G),[/math] [math]\alpha (G - A) = \alpha (G) - |A|.[/math] Это означает, что не существует рёбер, соединяющих вершины из [math]C(G - A)[/math] и [math]D(G - A)[/math]. Каждое максимальное паросочетание [math]M'[/math] графа [math]G - A[/math] покрывает все вершины множества [math]C(G)[/math], поэтому [math]M'[/math] содержит совершенное паросочетание графа [math]C[/math]. Тем самым, мы доказали пункт 1). 2) Из формулы [math] \alpha(G - A) = \alpha (G) - |A|[/math] следует, что [math]U1,{...},Un[/math]- компоненты связности графа [math]G - A[/math]. Для любой вершины [math]u \in Ui [/math]существует максимальное паросочетание [math]Mu[/math] графа [math]G - A[/math], не содержащее [math]u[/math]. Так как [math]Ui[/math] - компонента связности графа [math]G - A[/math], паросочетание [math]Mu[/math] содержит максимальное паросочетание графа [math]Di[/math] (разумеется, не покрывающее вершину [math]u[/math]). Следовательно, [math] \alpha (Di) = \alpha (Di - u) [/math] и по теореме Галлаи(выше) мы получаем, что граф [math]Di[/math] - фактор-критический. 3) Пусть [math]M[/math] - максимальное паросочетание графа [math]G[/math], а [math]M'[/math] получено из [math]M[/math] удалением всех рёбер, инцидентных вершинам множества [math]A[/math]. Тогда [math]|M'| \ge |M| - |A|[/math] и по формуле [math] \alpha (G - A) = \alpha (G) - |A|[/math] понятно, что [math]M'[/math] - максимальное паросочетание графа [math]G - A[/math]. Более того, из [math] \alpha (G - A) = \alpha (G) - |A|[/math] следует [math]|M'| = |M| - |A|[/math], а значит, все вершины множества [math]A[/math] покрыты в [math]M[/math] различными рёбрамию Так как [math]M'[/math] - максимальное паросочетание графа [math]G - A[/math], то по пунктам 1) и 2) очевидно, что [math]M'[/math] содержит совершенное паросочетание графа [math]C[/math] и почти совершенные паросочетания фактор-критических графов [math]D1,{...},Dn[/math]. Значит, рёбра паросочетания [math]M[/math] соединяют вершины [math]A[/math] с непокрытыми [math]M'[/math] вершинами различных компонент связности из [math]U1,{...},Un[/math]. 4) Из пункта 3) сразу же следуют оба равенства пункта 4).

[math]\triangleleft[/math]

Утверждение (следствие из теоремы):

граф G фактор-критический тогда и только тогда, когда U не пусто и U - единственное множество свидетелей Татта-Бержа для G