Декомпозиция Эдмондса-Галлаи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Структурная теорема Эдмондса-Галлаи)
Строка 15: Строка 15:
 
|about=Бержа
 
|about=Бержа
 
|statement=
 
|statement=
для любого графа G выполняется:<br>
+
Для любого графа G выполняется:<br>
 
<tex>def(G) = max_{S \subset V(G)} \{o(G - S) - |S|\}.</tex>
 
<tex>def(G) = max_{S \subset V(G)} \{o(G - S) - |S|\}.</tex>
 
}}
 
}}
Строка 23: Строка 23:
 
|about=Татта-Бержа
 
|about=Татта-Бержа
 
|statement=
 
|statement=
дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br>
+
Дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br>
 
<tex>\alpha (G) = min_{U \in V} \{1/2(|V|-|U|-o(G-U)\} </tex>
 
<tex>\alpha (G) = min_{U \in V} \{1/2(|V|-|U|-o(G-U)\} </tex>
 
}}
 
}}
Строка 30: Строка 30:
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
Множество <tex>S \subset V (G)</tex>, для которого <tex>o(G - S) - |S| = def(G) </tex> называется '''барьером'''.
+
Множество <tex>S \subset V (G)</tex>, для которого <tex>o(G - S) - |S| = def(G) </tex>, называется '''барьером'''.
 
}}
 
}}
  
Строка 38: Строка 38:
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
необходимые определения:
+
Необходимые определения:
 
[[Файл: Edmonds-Gallai.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены жирным]]
 
[[Файл: Edmonds-Gallai.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены жирным]]
 
* <tex>D(G) = \{v \in V |</tex> существует максимальное паросочетание, не покрывающее <tex> v\}</tex>
 
* <tex>D(G) = \{v \in V |</tex> существует максимальное паросочетание, не покрывающее <tex> v\}</tex>
Строка 58: Строка 58:
 
|about= Галлаи, о стабильности  
 
|about= Галлаи, о стабильности  
 
|statement=
 
|statement=
пусть <tex> a \in A(G).</tex> Тогда:  
+
Пусть <tex> a \in A(G).</tex> Тогда:  
 
* <tex>D(G - a) = D(G)</tex>  
 
* <tex>D(G - a) = D(G)</tex>  
 
* <tex>A(G - a) = A(G) \setminus \{a\}</tex>
 
* <tex>A(G - a) = A(G) \setminus \{a\}</tex>

Версия 18:04, 17 декабря 2013

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


Определение:
Дефицитом графа G мы будем называть величину:

[math]def(G) = V(G) - 2\alpha (G)[/math],
где [math]\alpha (G)[/math] - размер максимального поросочетания в [math]G[/math], а

[math]V(G)[/math] - множество вершин графа [math]G[/math]


Теорема (Бержа):
Для любого графа G выполняется:
[math]def(G) = max_{S \subset V(G)} \{o(G - S) - |S|\}.[/math]


Теорема (Татта-Бержа):
Дан граф [math]G[/math], размер максимального паросочетания в нем равен:
[math]\alpha (G) = min_{U \in V} \{1/2(|V|-|U|-o(G-U)\} [/math]


Определение:
Множество [math]S \subset V (G)[/math], для которого [math]o(G - S) - |S| = def(G) [/math], называется барьером.



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

Определение:
Необходимые определения:
Пример. Рёбра из паросочетания выделены жирным
  • [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

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

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]
Теорема (Галлаи, Эдмондс):
Пусть G - граф, [math]U1,{...},Un[/math] - компоненты связности графа [math]G(D(G))[/math] , [math]Di = G(Ui), C = G(C(G))[/math]. тогда:
Пример

1) Граф [math]C[/math] имеет совершенное паросочетание.
2) Графы [math]D1,{...},Dn[/math] - фактор-критические.
3) Любое максимальное паросочетание [math]M[/math] графа [math]G[/math] состоит из совершенного паросочетания графа [math]C[/math], почти совершенных паросочетаний графов [math]D1,{...},Dn[/math] и покрывает все вершины множества [math]A(G)[/math] рёбрами с концами в различных компонентах связности [math]U1,{...},Un[/math]

4) [math]def(G) = n - |A(G)|, 2\alpha (G) = v(G) + |A(G)| - n[/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]
Утверждение (следствие из теоремы):
[math]A(G)[/math] - барьер графа [math]G[/math]


Источники