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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Структурная теорема Эдмондса-Галлаи)
Строка 44: Строка 44:
 
Необходимые определения:
 
Необходимые определения:
 
[[Файл: EG_red.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены красным]]
 
[[Файл: EG_red.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены красным]]
* <tex>D(G) = \{v \in V |</tex> существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]], не покрывающее <tex> v\}</tex>
+
# <tex>D(G) = \{v \in V |</tex> существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]], не покрывающее <tex> v\}</tex>
* <tex>A(G) = N(D(G)) \setminus D(G)</tex>
+
# <tex>A(G) = N(D(G)) \setminus D(G)</tex>
* <tex>C(G) = V \setminus( D(G) \bigcup A(G) )</tex>
+
# <tex>C(G) = V \setminus( D(G) \bigcup A(G) )</tex>
* <tex> \alpha (G) </tex> - размер максимального паросочетания в <tex>G</tex>
+
# <tex> \alpha (G) </tex> - размер максимального паросочетания в <tex>G</tex>
 
}}
 
}}
  
Строка 68: Строка 68:
 
|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>
* <tex>C(G - a) = C(G)</tex>  
+
# <tex>C(G - a) = C(G)</tex>  
* <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
+
# <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
 
|proof=
 
|proof=
 
Достаточно доказать, что <tex>D(G - a) = D(G)</tex>. <br>
 
Достаточно доказать, что <tex>D(G - a) = D(G)</tex>. <br>
<tex>1)</tex> покажем, что <tex>D(G - a) \supset D(G)</tex> : <br>
+
'''1.''' покажем, что <tex>D(G - a) \supset D(G)</tex> : <br>
 
Пусть <tex>u \in D(G)</tex>. Тогда существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] <tex>M_u</tex> графа <tex>G</tex>, не покрывающее <tex>u</tex>. Поскольку любое максимальное паросочетание графа <tex>G</tex> покрывает a, то <tex> \alpha (G - a) = \alpha (G) - 1 </tex> и более того, если <tex> ax \in M_u </tex>, то <tex>M_u \setminus {ax} </tex> -  максимальное паросочетание графа <tex> G - a </tex>, не покрывающее <tex> u </tex>. Таким образом, <tex>D(G - a) \supset D(G) </tex>. <br>
 
Пусть <tex>u \in D(G)</tex>. Тогда существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] <tex>M_u</tex> графа <tex>G</tex>, не покрывающее <tex>u</tex>. Поскольку любое максимальное паросочетание графа <tex>G</tex> покрывает a, то <tex> \alpha (G - a) = \alpha (G) - 1 </tex> и более того, если <tex> ax \in M_u </tex>, то <tex>M_u \setminus {ax} </tex> -  максимальное паросочетание графа <tex> G - a </tex>, не покрывающее <tex> u </tex>. Таким образом, <tex>D(G - a) \supset D(G) </tex>. <br>
<tex>2)</tex>покажем, что <tex> D(G - a) \subset D(G)</tex>: <br>
+
'''2.''' покажем, что <tex> D(G - a) \subset D(G)</tex>: <br>
 
Предположим, что существует максимальное паросочетание <tex>M'</tex> графа <tex> G - a</tex>, не покрывающее вершину <tex>v not \in D(G)</tex>. Пусть <tex> w \in D(G) </tex> - смежная с <tex> a \in A(G)</tex> вершина, а <tex> M_w </tex>- максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> w </tex>. Так как <tex> v not \in D(G) </tex>, максимальное паросочетание <tex> M_w </tex> покрывает вершину <tex>v</tex>. Рассмотрим граф <tex> H = G(M_w \bigcup M') </tex> - очевидно, он является объединением нескольких путей и чётных циклов. Пусть <tex> U </tex> - компонента связности графа <tex> H </tex>, содержащая <tex>v</tex>. Так как <tex> dH(v) = 1 </tex>, то <tex> P = H(U) </tex> - путь с началом в вершине <tex>v</tex>. В пути <tex>P</tex> чередуются рёбра из <tex> M_w и M' </tex>, причём начинается путь ребром из <tex>M_w </tex>. Так как <tex> dH(a) = 1 </tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> M_w</tex>). Рассмотрим несколько случаев: <br>
 
Предположим, что существует максимальное паросочетание <tex>M'</tex> графа <tex> G - a</tex>, не покрывающее вершину <tex>v not \in D(G)</tex>. Пусть <tex> w \in D(G) </tex> - смежная с <tex> a \in A(G)</tex> вершина, а <tex> M_w </tex>- максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> w </tex>. Так как <tex> v not \in D(G) </tex>, максимальное паросочетание <tex> M_w </tex> покрывает вершину <tex>v</tex>. Рассмотрим граф <tex> H = G(M_w \bigcup M') </tex> - очевидно, он является объединением нескольких путей и чётных циклов. Пусть <tex> U </tex> - компонента связности графа <tex> H </tex>, содержащая <tex>v</tex>. Так как <tex> dH(v) = 1 </tex>, то <tex> P = H(U) </tex> - путь с началом в вершине <tex>v</tex>. В пути <tex>P</tex> чередуются рёбра из <tex> M_w и M' </tex>, причём начинается путь ребром из <tex>M_w </tex>. Так как <tex> dH(a) = 1 </tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> M_w</tex>). Рассмотрим несколько случаев: <br>
  
Строка 105: Строка 105:
 
Пусть G - граф, <tex>U_1,{...},U_n</tex> - компоненты связности графа <tex>G(D(G))</tex>, <tex>D_i = G(U_i), C = G(C(G))</tex>. тогда:
 
Пусть G - граф, <tex>U_1,{...},U_n</tex> - компоненты связности графа <tex>G(D(G))</tex>, <tex>D_i = G(U_i), C = G(C(G))</tex>. тогда:
  
1) Граф <tex>C</tex> имеет совершенное паросочетание.<br>
+
# Граф <tex>C</tex> имеет совершенное паросочетание.<br>
2) Графы <tex>D_1,{...},D_n</tex> - фактор-критические. <br>
+
# Графы <tex>D_1,{...},D_n</tex> - фактор-критические. <br>
3) Любое максимальное паросочетание <tex>M</tex> графа <tex>G</tex> состоит из совершенного паросочетания графа <tex>C</tex>, почти совершенных паросочетаний графов <tex>D_1,{...},D_n</tex> и покрывает все вершины множества <tex>A(G)</tex> рёбрами с концами в различных компонентах связности <tex>U_1,{...},U_n</tex> <br>
+
# Любое максимальное паросочетание <tex>M</tex> графа <tex>G</tex> состоит из совершенного паросочетания графа <tex>C</tex>, почти совершенных паросочетаний графов <tex>D_1,{...},D_n</tex> и покрывает все вершины множества <tex>A(G)</tex> рёбрами с концами в различных компонентах связности <tex>U_1,{...},U_n</tex> <br>
4) <tex>def(G) = n - |A(G)|, 2\alpha (G) = v(G) + |A(G)| - n</tex>.
+
# <tex>def(G) = n - |A(G)|, 2\alpha (G) = v(G) + |A(G)| - n</tex>.
  
 
|proof=
 
|proof=

Версия 17:45, 21 декабря 2013

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


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

[math]\mathrm{def}(G) = |V| - 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)} \{odd(G - S) - |S|\}.[/math]


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


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


Определение:
Пусть [math]X \subset V [/math]. Множeство соседей [math]X[/math] определим формулой: [math]N(X)= \{ y \in V: (x,y) \in E \}[/math]



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

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


Определение:
Граф [math]G[/math] называется Фактор-критическим, если для любой вершины [math]v \in G[/math] в графе [math]G[/math] существует полное паросочетание, не покрываеющее [math]v[/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] Тогда:
  1. [math]D(G - a) = D(G)[/math]
  2. [math]A(G - a) = A(G) \setminus \{a\}[/math]
  3. [math]C(G - a) = C(G)[/math]
  4. [math] \alpha (G - a) = \alpha (G) - 1.[/math]
Доказательство:
[math]\triangleright[/math]

Достаточно доказать, что [math]D(G - a) = D(G)[/math].
1. покажем, что [math]D(G - a) \supset D(G)[/math] :
Пусть [math]u \in D(G)[/math]. Тогда существует максимальное паросочетание [math]M_u[/math] графа [math]G[/math], не покрывающее [math]u[/math]. Поскольку любое максимальное паросочетание графа [math]G[/math] покрывает a, то [math] \alpha (G - a) = \alpha (G) - 1 [/math] и более того, если [math] ax \in M_u [/math], то [math]M_u \setminus {ax} [/math] - максимальное паросочетание графа [math] G - a [/math], не покрывающее [math] u [/math]. Таким образом, [math]D(G - a) \supset D(G) [/math].
2. покажем, что [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] M_w [/math]- максимальное паросочетание графа [math] G [/math], не покрывающее [math] w [/math]. Так как [math] v not \in D(G) [/math], максимальное паросочетание [math] M_w [/math] покрывает вершину [math]v[/math]. Рассмотрим граф [math] H = G(M_w \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] M_w и M' [/math], причём начинается путь ребром из [math]M_w [/math]. Так как [math] dH(a) = 1 [/math], то вершина a либо не принадлежит пути [math]P[/math], либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию [math] M_w[/math]). Рассмотрим несколько случаев:

случай а

a. Путь [math]P[/math] кончается ребром из [math] M'[/math] (см. рисунок)
Рассмотрим паросочетание [math]M_v = M_w \oplus E(P)[/math] (симметрическая разность [math] M_w и E(P)[/math]. то есть, рёбра, входящие ровно в одно из двух множеств). Очевидно, [math]M_v[/math] - максимальное паросочетание графа [math]G[/math], не покрывающее [math]v[/math], поэтому [math] v \in D(G)[/math], противоречие.

случай b

b. Путь [math]P[/math] кончается ребром из [math] M_w[/math], вершина a - конец пути [math]P[/math]. (см.рисунок)
Рассмотрим паросочетание [math]M_v∗ = (M_w \oplus E(P)) \bigcup \{aw\} [/math]. Тогда [math] M_v∗ [/math] - максимальное паросочетание графа [math] G [/math], не покрывающее [math] v [/math], поэтому [math] v \in D(G) [/math], противоречие.

случай c

c. Путь [math] P [/math] кончается ребром из [math] M_w, 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]U_1,{...},U_n[/math] - компоненты связности графа [math]G(D(G))[/math], [math]D_i = G(U_i), C = G(C(G))[/math]. тогда:
  1. Граф [math]C[/math] имеет совершенное паросочетание.
  2. Графы [math]D_1,{...},D_n[/math] - фактор-критические.
  3. Любое максимальное паросочетание [math]M[/math] графа [math]G[/math] состоит из совершенного паросочетания графа [math]C[/math], почти совершенных паросочетаний графов [math]D_1,{...},D_n[/math] и покрывает все вершины множества [math]A(G)[/math] рёбрами с концами в различных компонентах связности [math]U_1,{...},U_n[/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]U_1,{...},U_n[/math]- компоненты связности графа [math]G - A[/math]. Для любой вершины [math]u \in U_i[/math] существует максимальное паросочетание [math]M_u[/math] графа [math]G - A[/math], не содержащее [math]u[/math]. Так как [math]U_i[/math] - компонента связности графа [math]G - A[/math], паросочетание [math]M_u[/math] содержит максимальное паросочетание графа [math]D_i[/math] (разумеется, не покрывающее вершину [math]u[/math]). Следовательно, [math] \alpha (D_i) = \alpha (D_i - u) [/math] и по теореме Галлаи(выше) мы получаем, что граф [math]D_i[/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]U_1,{...},U_n[/math].

4) Из пункта 3) сразу же следуют оба равенства пункта 4).
[math]\triangleleft[/math]
Утверждение (следствие из теоремы):
[math]A(G)[/math] - барьер графа [math]G[/math]


Источники