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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 66 промежуточных версий 10 участников)
Строка 1: Строка 1:
 +
В этом направлении много усилий приложили Вильям Томас '''Татт''' (''William Thomas Tutte''), Клод '''Берж''' (''Claude Berge''), Джек '''Эдмондс''' (''Jack Edmonds'') и Тибор '''Галлаи''' (''Tibor Gallai'').
 
{{Определение  
 
{{Определение  
 +
|id = deficit
 
|definition=
 
|definition=
<tex>odd(G-U)</tex> - количество компонент связности нечетного размера в <tex> G[V - U]</tex>.}}
+
'''Дефицитом''' (англ. ''deficit'') графа <tex>G</tex> мы будем называть величину: <br>
 
 
{{Определение
 
|definition=
 
'''Дефицитом''' графа G мы будем называть величину: <br>
 
 
<tex>\mathrm{def}(G) = |V| - 2\alpha (G)</tex>, <br>
 
<tex>\mathrm{def}(G) = |V| - 2\alpha (G)</tex>, <br>
где <tex>\alpha (G)</tex> - размер максимального поросочетания в <tex>G</tex>, а <br>
+
где <tex>\alpha (G)</tex> {{---}} размер [[Теорема о максимальном паросочетании и дополняющих цепях#theorem1|максимального паросочетания]] в <tex>G</tex>, а <br>
<tex>V(G)</tex> - множество вершин графа <tex>G</tex>
+
<tex>V(G)</tex> {{---}} множество вершин графа <tex>G. </tex>
 +
}}
 +
{{Определение
 +
|definition =<tex>\mathrm{odd}({G})</tex> {{---}} число нечетных компонент связности в графе <tex>{G}</tex>, где '''нечетная компонента''' (англ. ''odd component'') {{---}} это [[Отношение связности, компоненты связности#def2|компонента связности]], содержащая нечетное число вершин.
 
}}
 
}}
  
 +
{{Лемма
 +
|statement= <tex>(n + |S| + odd(G \setminus S)) \; \equiv \; 0 \; ( mod \; 2) \; </tex>, где <tex>G</tex> {{---}} граф с <tex>n</tex> вершинами, <tex>S \subset {V}_{G}</tex>
 +
|proof=
 +
Удалим из графа <tex>G</tex> множество <tex>S</tex>, получим <tex>t</tex> компонент связности, содержащих <tex>k_1, k_2 ... k_t</tex> вершин соответственно.
 +
<tex>|S|\; + \; \sum_{i=1}^{k}k_i \; = \; n \; </tex>, так как в сумме это все вершины исходного графа <tex>G</tex>.
 +
Возьмем данное равенство по модулю два: <tex>(|S|\; + \; \sum_{i=1}^{k}k_i) \; \equiv \; n \; (mod \; 2)</tex>
 +
В сумме <tex>\sum_{i=1}^{k}(k_i \; mod \; 2)</tex> число единиц равно числу нечетных компонент <tex>odd(G \setminus S)</tex>. Таким образом, <tex> \forall S \in V : \; (odd(G \setminus S) + |S|) \; \equiv \; n \; (mod \; 2) \;</tex>.
 +
}}
  
 
{{Теорема
 
{{Теорема
 +
|id = Th_Berge
 
|about=Бержа
 
|about=Бержа
 
|statement=
 
|statement=
Для любого графа G выполняется:<br>
+
Для любого графа <tex>G</tex> выполняется:<br>
<tex>def(G) = max_{S \subset V(G)} \{odd(G - S) - |S|\}.</tex>
+
<tex>\mathrm{def}(G) = \max\limits_{S \subset V(G)} \{\mathrm{odd}(G - S) - |S|\}. </tex>
 +
|proof=
 +
<tex> \forall S \in V : \; (odd(G \setminus S) + |S|) \; \equiv \; n ( mod \; 2) \;</tex>
 +
 
 +
 
 +
Рассмотрим несколько случаев:
 +
 
 +
 
 +
1. Если <tex> \max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|) \; = 0 \; </tex>, тогда для любых <tex>S \in V: \; odd(G \setminus S) \leq |S| \; </tex>, следовательно выполнено условие [[Теорема Татта о существовании полного паросочетания|теоремы Татта]], значит, в графе есть совершенное паросочетание, то есть его дефицит равен нулю.
 +
 
 +
2. Если <tex> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; </tex>, тогда рассмотрим исходный граф <tex>G</tex> и полный граф <tex>K_k</tex>  с <tex>k</tex> вершинами, <tex>W</tex> - вершины <tex>K_k</tex>. Каждую вершину <tex>K_k</tex> соединим с каждой вершиной <tex>G</tex>. Получим граф <tex>H \; = \; K_k + G \;</tex>, докажем, что для него выполнено условие теоремы Татта. Докажем, что для любых <tex>S \in V_{H}: odd(H \setminus S) \; \leq \; |S| \; </tex>.
 +
Рассмотрим <tex>S \; \subset \; V_H\;</tex>:
 +
 
 +
* Если <tex>W \not\subset S</tex>, тогда поскольку граф <tex>K_k</tex> полный и все его вершины связаны с каждой вершиной графа <tex>G</tex>, то граф <tex>H</tex> связный и <tex>odd(H \setminus S) \; = \; 0 \;</tex> или <tex>odd(G \setminus S) \; = \; 1 \;</tex>.
 +
** В случае <tex>odd(H \setminus S) \; = \; 0 \; </tex> условие очевидно выполняется, так как для любых <tex>S \in G : 0 \; \leq \; |S| \;</tex>.
 +
** Рассмотрим случай <tex>odd(H \setminus S) \; = \; 1 \;</tex>, <tex>|V_H| \; = \; n \; + \; k \; = \; n \; + \; odd(G \setminus A) \; - \; |A| \; </tex>, где <tex>A \; = \; arg \max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|) \; </tex>. Разность <tex>odd(G \setminus A) \; - \; |A| \; </tex> имеет ту же четность, что и <tex>n</tex>, и <tex>odd(H \setminus S) \; = \; 1 \;</tex>, поэтому <tex>|V_H|</tex> четно, значит, по лемме, мощность <tex>S</tex> нечетна, следовательно она не равна нулю, значит, <tex> 1 \leq |S| </tex>.
 +
 
 +
 
 +
* Если <tex>W \subset S \;</tex>, то <tex>odd(H \setminus S) \; = \; odd(G \setminus (S \cap V)) \; = odd(G \setminus (S \cap V)) \; - \; |S \cap V| \; + \; |S \cap V| \; \leq \; |S \cap V| \; + \; k \leq |S| \; </tex>, так как <tex> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; </tex>. Таким образом, для графа <tex>H</tex> выполнено условие теоремы Татта, следовательно в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе <tex>H</tex>, удалим вершины <tex>W</tex> из графа <tex>H</tex>. Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин <tex>k</tex>, значит, <tex>def(G) \; \leq \; k</tex>. Удалим множество вершин <tex>A \; = \; arg \max\limits_{S \in V}(odd(H \setminus S) \; - \; |S|) \; </tex> из графа <tex>G\;</tex>. Заметим, что после удаления в графе осталось <tex>odd(G \setminus A)\; </tex> нечетных компонент и образовались новые непокрытые вершины, но при этом число нечетных компонент больше числа удаленных на <tex>k</tex>. Значит, хотя бы <tex>k</tex> нечетных компонент содержали исходно непокрытую вершину, следовательно <tex>def(G) \; \geq \; k \; </tex>. Из <tex>def(G) \; \leq \; k</tex> и <tex>def(G) \; \geq \; k \; </tex> следует <tex>def(G) \; = \; k \; </tex>.
 
}}
 
}}
  
  
 
{{Теорема
 
{{Теорема
 +
|id = theorem_Tatt_Berge
 
|about=Татта-Бержа
 
|about=Татта-Бержа
 
|statement=
 
|statement=
 
Дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br>
 
Дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br>
<tex>\alpha (G) = min_{U \in V} \{1/2(|V|-|U|-odd(G-U)\} </tex>
+
<tex>\mathrm{\alpha}(G) = \min\limits_{U \in V} \{\dfrac{1}{2}(|V|+|U|-\mathrm{odd}(G - U)\}. </tex>
 +
|proof=
 +
Предположим <tex>G</tex> {{---}} связный, иначе мы можем применить индукцию к компонентам <tex>G</tex>. Приведем доказательство по индукции по числу вершин в графе. <br>
 +
<u> ''База  индукции:''</u> <br>
 +
Очевидно, для <tex> n = 1 </tex> утверждение верно. <br>
 +
<u> ''Индукционный переход:''</u> <br>
 +
Рассмотрим два случая:
 +
# <tex>G</tex> {{---}} содержит вершину <tex>v</tex> покрытую всеми максимальными паросочетаниями (например средняя вершина)
 +
#: Тогда <tex> \mathrm{\alpha}(G - v) = \mathrm{\alpha}(G) - 1 </tex>.
 +
#: По индукции, формула Татта-Берджа содержит <tex>G - v</tex> для некоторого множества  <tex>U'</tex>. Пусть <tex>U = U' \bigcup v</tex>. Тогда:
 +
#: <tex> \mathrm{\alpha}(G) = \mathrm{\alpha}(G - v) + 1 = \dfrac{1}{2}(|V - v|+|U - v| - \mathrm{odd}(G - v - (U - v))) + 1 = </tex>
 +
#: <tex> = \dfrac{1}{2}(|V| - 1 + |U|- 1 - \mathrm{odd}(G - U)) + 1 = \dfrac{1}{2}(|V|+|U| - \mathrm{odd}(G - U)). </tex>
 +
#:
 +
# Для каждой вершины <tex>v</tex> есть максимальное паросочетание <tex>M</tex> которое не покрывает <tex>v</tex> (например <tex>C_3</tex>)
 +
#:
 +
#: Покажем, что существует паросочетание размера <tex> \dfrac{1}{2}(|V| - 1) </tex>, из которого следует теорема (при <tex> U = \emptyset </tex>).
 +
#: <u> ''От противного:''</u>
 +
#: Предположим что любое максимальная паросочетание <tex> M </tex> не покрывает, по крайней мере, две различные вершины <tex> u </tex> и <tex> v </tex>. Среди всех таких <tex> (M, u, v) </tex> выберем их так, что <tex> \mathrm{d}(u, u) </tex> в <tex> G </tex> {{---}} минимально.
 +
#: Если <tex> \mathrm{d}(u, u) = 1 </tex>, то <tex> u </tex> и <tex> v </tex> являются смежными, и, следовательно, мы можем увеличить <tex> M </tex>, что противоречит его максимальности.
 +
#: Значит <tex> \mathrm{d}(u, u) \geqslant 2 </tex>, и, следовательно, мы можем выбрать промежуточную вершину <tex> t </tex> на пути <tex> u-v </tex> и <tex> N </tex> максимальное паросочетание, такое что симметрическая разность с <tex> M </tex> минимальна. Так как <tex> (M, u, v) </tex> минимально, то <tex> N </tex> должно охватывать <tex> u </tex> и <tex> v </tex> так, что есть другая вершина <tex> x </tex>, покрытая только в <tex> M </tex>.
 +
#: Пусть <tex> y </tex> будет вершиной покрытой с <tex> x </tex> в <tex> M </tex> и заметим <tex> y \neq t </tex> (иначе можно было бы добавить к <tex> N </tex>). Пусть <tex> z </tex> будет вершиной покрытой с <tex> y </tex> в <tex> N </tex> и заметим <tex> z \neq x </tex> (так как <tex> x </tex> не покрыто в <tex> N </tex>). Тогда <tex> N - yz + xy </tex> {{---}} паросочетание, которое имеет с <tex> M </tex> меньшую симметрическую разность, что противоречит выбору <tex> N </tex>.
 +
}}
 +
{{Определение
 +
|id=barrier
 +
|definition=
 +
Множество <tex>S \subset V (G)</tex>, для которого <tex>\mathrm{odd}(G - S) - |S| = \mathrm{def}(G) </tex>, называется '''барьером''' (англ. ''barrier'').
 +
}}
 +
{{Определение
 +
|definition=Пусть <tex>X \subset V </tex>. '''Множeство соседей''' (англ. ''neighbors'') <tex>X</tex> определим формулой:  <tex>N(X)= \{  y \in V:(x,y) \in E \}</tex>
 
}}
 
}}
  
  
 +
==Структурная теорема Эдмондса-Галлаи==
 
{{Определение  
 
{{Определение  
 +
|neat = 1
 
|definition=
 
|definition=
Множество <tex>S \subset V (G)</tex>, для которого <tex>odd(G - S) - |S| = def(G) </tex>, называется '''барьером'''.
+
Структурные единицы декопозиции:
 +
# <tex>D(G) = \{v \in V \mid </tex> существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]], не покрывающее <tex> v\}</tex>
 +
# <tex>A(G) = N(D(G)) \setminus D(G)</tex>
 +
# <tex>C(G) = V \setminus(D(G) \bigcup A(G))</tex>
 +
# <tex> \alpha (G) </tex> {{---}} размер максимального паросочетания в <tex> G. </tex>
 
}}
 
}}
 
+
[[Файл: EG_red.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены красным]]
 
 
 
 
=Структурная теорема Эдмондса-Галлаи=
 
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
Необходимые определения:
+
Граф <tex>G</tex> называется '''фактор-критическим''' (англ. ''factor-critical graph''), если для любой вершины <tex>v \in G</tex> в графе <tex>G \setminus {v}</tex> существует [[Теорема Холла#def1|совершенное паросочетание]].
[[Файл: Edmonds-Gallai.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены жирным]]
 
* <tex>D(G) = \{v \in V |</tex> существует максимальное паросочетание, не покрывающее <tex> v\}</tex>
 
* <tex>A(G) = N(D(G)) \setminus D(G)</tex>
 
* <tex>C(G) = V \setminus( D(G) \bigcup A(G) )</tex>
 
* <tex> \alpha (G) </tex> - размер максимального паросочетания в <tex>G</tex>
 
 
}}
 
}}
 
 
  
 
{{Теорема
 
{{Теорема
 +
|id = theorem_Gallai
 
|about=Галлаи
 
|about=Галлаи
 
|statement=
 
|statement=
<tex>G</tex> - фактор-критический граф <tex> \Leftrightarrow </tex> <br>
+
<tex>G</tex> {{---}} фактор-критический граф <tex> \Leftrightarrow </tex> <br>
<tex>G</tex> - связен и для любой вершины<tex> u \in V(G) </tex> выполняется равенство <tex> \alpha (G - u) = \alpha  (G)</tex>.
+
<tex>G</tex> {{---}} связен и для любой вершины <tex>u \in V(G) </tex> выполняется равенство <tex> \alpha (G - u) = \alpha  (G)</tex>.
 
}}
 
}}
 +
  
 
{{Лемма
 
{{Лемма
|about= Галлаи, о стабильности  
+
|id = stability_lemma
 +
|about= Галлаи, о стабильности (англ. ''stability lemma'')
 
|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>
+
[[Файл: Gallai-lema-a.png|150px|thumb|right|Случай '''а''']]
Пусть <tex>u \in D(G)</tex>. Тогда существует максимальное паросочетание <tex> Mu </tex> графа <tex>G</tex>, не покрывающее <tex>u</tex>. Поскольку любое максимальное паросочетание графа <tex>G</tex> покрывает a, то <tex> \alpha (G - a) = \alpha (G) - 1 </tex> и более того, если <tex> ax \in Mu </tex>, то <tex>Mu \setminus {ax} </tex> -  максимальное паросочетание графа <tex> G - a </tex>, не покрывающее <tex> u </tex>. Таким образом, <tex>D(G - a) \supset D(G) </tex>. <br>
+
[[Файл: Gallai-lema-b.png|150px|thumb|right|Случай '''b''']]
<tex>2)</tex>покажем, что <tex> D(G a) \subset D(G)</tex>: <br>
+
[[Файл: Gallai-lema-с.png|150px|thumb|right|Случай '''c''']]
Предположим, что существует максимальное паросочетание <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> Mw </tex>- максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> w </tex>. Так как <tex> v not \in D(G) </tex>, максимальное паросочетание <tex> Mw </tex> покрывает вершину <tex>v</tex>. Рассмотрим граф <tex> H = G(Mw \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> Mw и M' </tex>, причём начинается путь ребром из <tex>Mw </tex> . Так как <tex> dH(a) = 1 </tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> Mw</tex>). Рассмотрим несколько случаев: <br>
+
# Покажем, что <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> покрывает <tex>a</tex>, то <tex> \alpha (G - a) = \alpha (G) - 1 </tex> и более того, если, для некоторой вершины <tex>x \in D(G)</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> D(G - a) \subset D(G)</tex>: <br>
 +
Предположим, что существует максимальное паросочетание <tex>M'</tex> графа <tex> G - a</tex>, не покрывающее вершину <tex>v</tex> <tex> \notin 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</tex> <tex> \notin 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> deg_H(v) = 1 </tex> (степень вершины), то <tex> P = H(U) </tex> {{---}} путь с началом в вершине <tex>v</tex>. В пути <tex>P</tex> чередуются рёбра из <tex> M_w</tex> и <tex>M' </tex>, причём начинается путь ребром из <tex>M_w </tex>. Так как <tex> deg_H(a) = 1 </tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> M_w</tex>). Рассмотрим несколько случаев: <br>
  
[[Файл: Gallai-lema-a.png|150px|thumb|right|случай '''а''']]
 
 
'''a.''' Путь <tex>P</tex> кончается ребром из <tex> M'</tex> (см. рисунок)<br>
 
'''a.''' Путь <tex>P</tex> кончается ребром из <tex> M'</tex> (см. рисунок)<br>
Рассмотрим паросочетание <tex>Mv = Mw \oplus E(P)</tex> (симметрическая разность
+
Рассмотрим паросочетание <tex>M_v = M_w \oplus E(P)</tex> (симметрическая разность
<tex> Mw и E(P)</tex>. то есть, рёбра, входящие ровно в одно из двух множеств).
+
<tex> M_w</tex> и <tex>E(P)</tex>. то есть, рёбра, входящие ровно в одно из двух множеств).
Очевидно, <tex>Mv</tex> - максимальное паросочетание графа <tex> G</tex>, не покрывающее <tex> v</tex>, поэтому <tex> v \in D(G)</tex>, противоречие. <br>
+
Очевидно, <tex>M_v</tex> {{---}} максимальное паросочетание графа <tex>G</tex>, не покрывающее <tex>v</tex>, поэтому <tex> v \in D(G)</tex>, противоречие. <br>
  
[[Файл: Gallai-lema-b.png|150px|thumb|right|случай '''b''']]
+
'''b.''' Путь <tex>P</tex> кончается ребром из <tex> M_w</tex>, вершина <tex>a</tex> {{---}} конец пути <tex>P</tex>. (см.рисунок)<br>
'''b.''' Путь <tex>P</tex> кончается ребром из <tex> Mw</tex>, вершина a - конец пути <tex>P</tex>. (см.рисунок)<br>
+
Рассмотрим паросочетание <tex>M_v∗ = (M_w \oplus E(P)) \bigcup \{aw\} </tex>. Тогда <tex> M_v∗ </tex> {{---}} максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> v </tex>, поэтому <tex> v \in D(G) </tex>, противоречие.
Рассмотрим паросочетание <tex>Mv∗ = (Mw \oplus E(P)) \bigcup \{aw\} </tex>. Тогда <tex> Mv∗ </tex> - максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> v </tex>, поэтому <tex> v \in D(G) </tex>, противоречие.
 
  
[[Файл: Gallai-lema-с.png|150px|thumb|right|случай '''c''']]
+
'''c.'''  Путь <tex> P </tex> кончается ребром из <tex> M_w, a \in V(P) </tex> (см. рисунок)
'''c.'''  Путь <tex> P </tex> кончается ребром из <tex> Mw, a \in V(P) </tex> (см. рисунок)
 
 
Рассмотрим паросочетание <tex> M'' = M \oplus E(P) </tex>. Тогда <tex> |M''| = |M'| + 1 </tex>, причём <tex>M'' \subset E(G - a)</tex>. Противоречие с максимальностью паросочетания <tex>M'</tex>.
 
Рассмотрим паросочетание <tex> M'' = M \oplus E(P) </tex>. Тогда <tex> |M''| = |M'| + 1 </tex>, причём <tex>M'' \subset E(G - a)</tex>. Противоречие с максимальностью паросочетания <tex>M'</tex>.
  
 +
Таким образом, наше предположение невозможно и <tex>D(G - a) \subset D(G)</tex>.
 +
А значит, <tex>D(G - a) = D(G)</tex>.
 +
 +
 +
Так как <tex>D(G - a) = D(G)</tex>, то все вершины, которые были соседями <tex>D(G)</tex>, таковыми и остались. Однако, по условию <tex> a \in A(G)</tex>, значит <tex>A(G - a) = A(G) \setminus \{a\}</tex>.
 +
 +
 +
Так же заметим, что <tex>C(G - a) = V(G - a) \setminus (D(G - a) \cup A(G - a)) = V(G - a) \setminus (D(G) \cup (A(G) \setminus \{a\}))</tex><tex> = V(G) \setminus (D(G) \cup A(G)) = C(G)</tex>
  
Таким образом, наше предположение невозможно и <tex>D(G - a) \subset D(G)</tex>.
 
  
А значит, <tex>D(G - a) = D(G)</tex>.
+
Наконец, так как <tex> a \in A(G)</tex>, то все максимальные паросочетания в <tex>G</tex> включали <tex>a</tex>. Следовательно, <tex>\alpha (G - a) < \alpha (G)</tex>. Заметим, что, взяв любое максимальное паросочетания в <tex>G</tex> и удалив ребро инцидентное <tex>a</tex>, мы получим паросочетание <tex>M'</tex>, которое на 1 меньше исходного, при этом <tex>M' \in E(G - a)</tex>. В свою очередь, это самое большое паросочетание, которое мы могли теоретически получить в <tex>G - a</tex>. Следовательно, <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
 
}}
 
}}
  
  
 
{{Теорема
 
{{Теорема
 +
|id = theorem_Gallai_Edmonds
 
|about = Галлаи, Эдмондс
 
|about = Галлаи, Эдмондс
 
|statement=
 
|statement=
Пусть G - граф, <tex>U1,{...},Un</tex> - компоненты связности графа <tex>G(D(G))</tex> , <tex>Di = G(Ui), C = G(C(G))</tex>. тогда:
+
Пусть <tex>G</tex> {{---}} граф, <tex>U_1\ldots U_n</tex> {{---}} компоненты связности графа <tex>G(D(G))</tex>, <tex>D_i = G(U_i), C = G(C(G))</tex>. Тогда:
 
+
# Граф <tex>C</tex> имеет совершенное паросочетание.<br>
1) Граф <tex>C</tex> имеет совершенное паросочетание.<br>
+
# Графы <tex>D_1\ldots D_n</tex> {{---}} фактор-критические. <br>
2) Графы <tex>D1,{...},Dn</tex> - фактор-критические. <br>
+
# Любое максимальное паросочетание <tex>M</tex> графа <tex> G </tex> состоит из совершенного паросочетания графа <tex> C </tex>, почти совершенных паросочетаний графов <tex> D_1\ldots D_n </tex> и покрывает все вершины множества <tex> A(G) </tex> рёбрами с концами в различных компонентах связности <tex> U_1\ldots U_n. </tex> <br>
3) Любое максимальное паросочетание <tex>M</tex> графа <tex>G</tex> состоит из совершенного паросочетания графа <tex>C</tex>, почти совершенных паросочетаний графов <tex>D1,{...},Dn</tex> и покрывает все вершины множества <tex>A(G)</tex> рёбрами с концами в различных компонентах связности <tex>U1,{...},Un</tex> <br>
+
# <tex>\mathrm{def}(G) = n - |A(G)|.</tex> <br>
4) <tex>def(G) = n - |A(G)|, 2\alpha (G) = v(G) + |A(G)| - n</tex>.
+
# <tex>2\mathrm{\alpha}(G) = v(G) + |A(G)| - n</tex>.
 
 
 
|proof=
 
|proof=
 
[[Файл: Edmonds-Gallai_2.png|300px|thumb|right|Пример]]
 
[[Файл: Edmonds-Gallai_2.png|300px|thumb|right|Пример]]
1) Последовательно удаляя вершины множества<tex> A = A(G)</tex>, по лемме о стабильности мы получим:
+
# Последовательно удаляя вершины множества <tex>A = A(G)</tex>, по лемме о стабильности мы получим:
* <tex>D(G - A) = D(G),</tex>  
+
#:* <tex>D(G - A) = D(G),</tex>  
* <tex>A(G - A) = \O, </tex>
+
#:* <tex>A(G - A) = \O, </tex>
* <tex>C(G - A) = C(G),</tex>
+
#:* <tex>C(G - A) = C(G),</tex>
* <tex>\alpha (G - A) = \alpha (G) - |A|.</tex>
+
#:* <tex>\alpha (G - A) = \alpha (G) - |A|.</tex>
 +
#:
 +
#:Это означает, что не существует рёбер, соединяющих вершины из <tex>C(G - A)</tex> и <tex>D(G - A)</tex>. Каждое максимальное паросочетание <tex>M'</tex> графа <tex>G - A</tex> покрывает все вершины множества <tex>C(G)</tex>, поэтому <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex>. Тем самым, мы доказали пункт <tex>1)</tex>.
 +
#:
 +
# Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U_1\ldots U_n</tex> {{---}} компоненты связности графа <tex>G - A</tex>. Для любой вершины <tex>u \in U_i</tex> существует максимальное паросочетание <tex>M_u</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. Так как <tex>U_i</tex> {{---}} компонента связности графа <tex>G - A</tex>, паросочетание <tex>M_u</tex> содержит максимальное паросочетание графа <tex>D_i</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, <tex> \alpha (D_i) = \alpha (D_i - u) </tex> и по теореме Галлаи (мы получаем, что граф <tex>D_i</tex> {{---}} фактор-критический.
 +
#:
 +
# Пусть <tex>M</tex> {{---}} максимальное паросочетание графа <tex>G</tex>, а <tex>M'</tex> получено из <tex>M</tex> удалением всех рёбер, инцидентных вершинам множества <tex>A</tex>. Тогда <tex>|M'| \geqslant |M| - |A|</tex> и по формуле <tex> \alpha (G - A) = \alpha (G) - |A|</tex> понятно, что <tex>M'</tex> {{---}} максимальное паросочетание графа <tex>G - A</tex>. Более того, из <tex> \alpha (G - A) = \alpha (G) - |A|</tex> следует <tex>|M'| = |M| - |A|</tex>, а значит, все вершины множества <tex>A</tex> покрыты в <tex>M</tex> различными рёбрами. Так как <tex>M'</tex> {{---}} максимальное паросочетание графа <tex>G - A</tex>, то по пунктам <tex>1)</tex> и <tex>2)</tex> очевидно, что <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex> и почти совершенные паросочетания фактор-критических графов <tex>D_1\ldots D_n</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U_1\ldots U_n</tex>.
 +
# Из пункта <tex>3)</tex> сразу же следуют равенства пункта <tex>4)</tex> и <tex>5)</tex>.
 +
}}
  
Это означает, что не существует рёбер, соединяющих вершины из <tex>C(G - A)</tex> и <tex>D(G - A)</tex>. Каждое максимальное паросочетание <tex>M'</tex> графа <tex>G - A</tex> покрывает все вершины множества <tex>C(G)</tex>, поэтому <tex>M'</tex> содержит
+
{{Утверждение
совершенное паросочетание графа <tex>C</tex>. Тем самым, мы доказали пункт 1).
+
|about=следствие из теоремы
 +
|statement=
 +
<tex>A(G)</tex> {{---}} '''барьер''' графа <tex>G</tex>
 +
}}
 +
 
 +
{{Лемма
 +
|id = barier_struct1
 +
|about = о связи барьера с <tex>D(G)</tex>
 +
|statement= Для любого барьера <tex>B</tex> графа <tex>G</tex> верно, что <tex>B\cap D(G) = \varnothing</tex>
 +
|proof= Рассмотрим <tex>U_{1}, U_{2},  \ldots U_{n}</tex> {{---}} нечётные компоненты связанности <tex>G \setminus B</tex>, <tex>\ M</tex> {{---}} максимальное паросочетание в <tex>G</tex>. <tex>\forall\ U_{i}\ \exists x \in U_{i}: x</tex> не покрыта <tex>\ M</tex> или <tex>xv \in M \land v \in B</tex>. Всего графе не покрыто хотя бы <tex>odd(G\setminus B) - |B|</tex> вершин. Однако, так как <tex>B</tex> {{---}} барьер, непокрыто '''ровно''' столько вершин. Следовательно, любое максимальное паросочетание не покрывает только вершины из <tex>G \setminus B</tex>, а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из <tex>D(G)</tex> не могла оказаться в барьере.
 +
}}
  
2) Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U1,{...},Un</tex>- компоненты связности графа <tex>G - A</tex>. Для любой вершины <tex>u \in Ui </tex>существует максимальное паросочетание <tex>Mu</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. Так как <tex>Ui</tex> -  компонента связности графа <tex>G - A</tex>, паросочетание <tex>Mu</tex> содержит максимальное паросочетание графа <tex>Di</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, <tex> \alpha (Di) = \alpha (Di - u) </tex> и по теореме Галлаи(выше) мы получаем, что граф <tex>Di</tex> - фактор-критический.
+
{{Утверждение
 +
|id = barier_struct1a
 +
|about=Следствие из леммы
 +
|statement=В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами <tex>G \setminus B</tex>
 +
|proof=Так как для барьера <tex>B</tex> верно, что <tex>odd(G\setminus B) - |B|=def(G) \geqslant 0</tex>, то ровно <tex>|B|</tex> вершин из нечётных компонент <tex>G \setminus B</tex> покрыты рёбрами <tex>xv \in M \land v \in B</tex>
 +
}}
  
3) Пусть <tex>M</tex> - максимальное паросочетание графа <tex>G</tex>, а <tex>M'</tex> получено из <tex>M</tex> удалением всех рёбер, инцидентных вершинам множества <tex>A</tex>. Тогда <tex>|M'| \ge |M| - |A|</tex> и по формуле <tex> \alpha (G - A) = \alpha (G) - |A|</tex> понятно, что <tex>M'</tex> - максимальное паросочетание графа <tex>G - A</tex>. Более того, из <tex> \alpha (G - A) = \alpha (G) - |A|</tex> следует <tex>|M'| = |M| - |A|</tex>, а значит, все вершины множества <tex>A</tex> покрыты в <tex>M</tex> различными рёбрами. Так как <tex>M'</tex> - максимальное паросочетание графа <tex>G - A</tex>, то по пунктам 1) и 2) очевидно, что <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex> и почти совершенные паросочетания фактор-критических графов <tex>D1,{...},Dn</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U1,{...},Un</tex>.
+
{{Лемма
4) Из пункта 3) сразу же следуют оба равенства пункта 4).
+
|id = barier_struct2
 +
|about = о дополнении барьера
 +
|statement= Пусть <tex>x\in A(G)\cup C(G),\ G'=G\setminus x,\ B'</tex> {{---}} барьер графа <tex>G'</tex>. Тогда <tex>B=B'\cup x</tex> {{---}} барьер графа <tex>G</tex>
 +
|proof= Так как <tex>x \notin D(G)</tex>, то для любого максимального паросочетания <tex>M: x \in M</tex>. Следовательно, <tex>|M'| = |M| - 1</tex>, где <tex>M'</tex> {{---}} максимальное паросочетание в <tex>G'</tex>.
  
 +
<tex>def(G') = (|V| - 1)- 2 \cdot |M'| = |V| - 2 \cdot |M| + 1 = def(G) + 1</tex>
  
}}
+
<tex>odd(G - (B'\cup x)) = odd(G' - B') = </tex><tex>|B'| + def(G') = |B'| + 1 + def(G) = |B'\cup x| + def(G)</tex>
 +
Отсюда следует, что <tex>B</tex> {{---}} барьер графа <tex>G</tex>.
 +
}}
  
{{Утверждение
+
{{Теорема
|about=следствие из теоремы
+
|id=barier_struct3
|statement=
+
|about=о структуре барьера
<tex>A(G)</tex> - '''барьер''' графа <tex>G</tex>
+
|statement=Любой барьер графа состоит только из вершин <tex>A(G)\cup C(G)</tex>, причём каждая вершина из этого множества входит в какой-то барьер
 +
|proof=По лемме о связи барьера с <tex>D(G)</tex> мы знаем, что в барьере нет вершин вершин из <tex>D(G)</tex>. По лемме о дополнение барьера мы можем взять любую вершину из <tex>A(G)\cup C(G)</tex>, удалить из графа, и с помощью барьера нового графа получить барьер исходного, включающий данную вершину.
 
}}
 
}}
  
 +
== См. также ==
 +
* [[Теорема Татта о существовании полного паросочетания]]
 +
* [[Лапы и минимальные по включению барьеры в графе]]
 +
* [[Пересечение всех максимальных по включению барьеров]]
  
== Источники ==
+
== Источники информации==
 
*[http://www.people.vcu.edu/~dcranston/691/edmonds-gallai.pdf Edmonds-Gallai Decomposition and Factor-Critical Graphs]
 
*[http://www.people.vcu.edu/~dcranston/691/edmonds-gallai.pdf Edmonds-Gallai Decomposition and Factor-Critical Graphs]
*[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf Д.В Карпов - теория графов]
+
*[http://immorlica.com/combOpt/lec2.pdf Edmonds-Gallai Decomposition, Edmonds’ Algorithm]
 +
*[https://www.youtube.com/watch?v=1KggxCJZFRg {{---}} Лекция А.С. Станкевича]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Задача о паросочетании]]
 
[[Категория:Задача о паросочетании]]

Текущая версия на 19:35, 4 сентября 2022

В этом направлении много усилий приложили Вильям Томас Татт (William Thomas Tutte), Клод Берж (Claude Berge), Джек Эдмондс (Jack Edmonds) и Тибор Галлаи (Tibor Gallai).

Определение:
Дефицитом (англ. deficit) графа [math]G[/math] мы будем называть величину:

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

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


Определение:
[math]\mathrm{odd}({G})[/math] — число нечетных компонент связности в графе [math]{G}[/math], где нечетная компонента (англ. odd component) — это компонента связности, содержащая нечетное число вершин.


Лемма:
[math](n + |S| + odd(G \setminus S)) \; \equiv \; 0 \; ( mod \; 2) \; [/math], где [math]G[/math] — граф с [math]n[/math] вершинами, [math]S \subset {V}_{G}[/math]
Доказательство:
[math]\triangleright[/math]

Удалим из графа [math]G[/math] множество [math]S[/math], получим [math]t[/math] компонент связности, содержащих [math]k_1, k_2 ... k_t[/math] вершин соответственно. [math]|S|\; + \; \sum_{i=1}^{k}k_i \; = \; n \; [/math], так как в сумме это все вершины исходного графа [math]G[/math]. Возьмем данное равенство по модулю два: [math](|S|\; + \; \sum_{i=1}^{k}k_i) \; \equiv \; n \; (mod \; 2)[/math]

В сумме [math]\sum_{i=1}^{k}(k_i \; mod \; 2)[/math] число единиц равно числу нечетных компонент [math]odd(G \setminus S)[/math]. Таким образом, [math] \forall S \in V : \; (odd(G \setminus S) + |S|) \; \equiv \; n \; (mod \; 2) \;[/math].
[math]\triangleleft[/math]
Теорема (Бержа):
Для любого графа [math]G[/math] выполняется:
[math]\mathrm{def}(G) = \max\limits_{S \subset V(G)} \{\mathrm{odd}(G - S) - |S|\}. [/math]
Доказательство:
[math]\triangleright[/math]

[math] \forall S \in V : \; (odd(G \setminus S) + |S|) \; \equiv \; n ( mod \; 2) \;[/math]


Рассмотрим несколько случаев:


1. Если [math] \max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|) \; = 0 \; [/math], тогда для любых [math]S \in V: \; odd(G \setminus S) \leq |S| \; [/math], следовательно выполнено условие теоремы Татта, значит, в графе есть совершенное паросочетание, то есть его дефицит равен нулю.

2. Если [math] \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; [/math], тогда рассмотрим исходный граф [math]G[/math] и полный граф [math]K_k[/math] с [math]k[/math] вершинами, [math]W[/math] - вершины [math]K_k[/math]. Каждую вершину [math]K_k[/math] соединим с каждой вершиной [math]G[/math]. Получим граф [math]H \; = \; K_k + G \;[/math], докажем, что для него выполнено условие теоремы Татта. Докажем, что для любых [math]S \in V_{H}: odd(H \setminus S) \; \leq \; |S| \; [/math]. Рассмотрим [math]S \; \subset \; V_H\;[/math]:

  • Если [math]W \not\subset S[/math], тогда поскольку граф [math]K_k[/math] полный и все его вершины связаны с каждой вершиной графа [math]G[/math], то граф [math]H[/math] связный и [math]odd(H \setminus S) \; = \; 0 \;[/math] или [math]odd(G \setminus S) \; = \; 1 \;[/math].
    • В случае [math]odd(H \setminus S) \; = \; 0 \; [/math] условие очевидно выполняется, так как для любых [math]S \in G : 0 \; \leq \; |S| \;[/math].
    • Рассмотрим случай [math]odd(H \setminus S) \; = \; 1 \;[/math], [math]|V_H| \; = \; n \; + \; k \; = \; n \; + \; odd(G \setminus A) \; - \; |A| \; [/math], где [math]A \; = \; arg \max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|) \; [/math]. Разность [math]odd(G \setminus A) \; - \; |A| \; [/math] имеет ту же четность, что и [math]n[/math], и [math]odd(H \setminus S) \; = \; 1 \;[/math], поэтому [math]|V_H|[/math] четно, значит, по лемме, мощность [math]S[/math] нечетна, следовательно она не равна нулю, значит, [math] 1 \leq |S| [/math].


  • Если [math]W \subset S \;[/math], то [math]odd(H \setminus S) \; = \; odd(G \setminus (S \cap V)) \; = odd(G \setminus (S \cap V)) \; - \; |S \cap V| \; + \; |S \cap V| \; \leq \; |S \cap V| \; + \; k \leq |S| \; [/math], так как [math] \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; [/math]. Таким образом, для графа [math]H[/math] выполнено условие теоремы Татта, следовательно в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе [math]H[/math], удалим вершины [math]W[/math] из графа [math]H[/math]. Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин [math]k[/math], значит, [math]def(G) \; \leq \; k[/math]. Удалим множество вершин [math]A \; = \; arg \max\limits_{S \in V}(odd(H \setminus S) \; - \; |S|) \; [/math] из графа [math]G\;[/math]. Заметим, что после удаления в графе осталось [math]odd(G \setminus A)\; [/math] нечетных компонент и образовались новые непокрытые вершины, но при этом число нечетных компонент больше числа удаленных на [math]k[/math]. Значит, хотя бы [math]k[/math] нечетных компонент содержали исходно непокрытую вершину, следовательно [math]def(G) \; \geq \; k \; [/math]. Из [math]def(G) \; \leq \; k[/math] и [math]def(G) \; \geq \; k \; [/math] следует [math]def(G) \; = \; k \; [/math].
[math]\triangleleft[/math]


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

Предположим [math]G[/math] — связный, иначе мы можем применить индукцию к компонентам [math]G[/math]. Приведем доказательство по индукции по числу вершин в графе.
База индукции:
Очевидно, для [math] n = 1 [/math] утверждение верно.
Индукционный переход:
Рассмотрим два случая:

  1. [math]G[/math] — содержит вершину [math]v[/math] покрытую всеми максимальными паросочетаниями (например средняя вершина)
    Тогда [math] \mathrm{\alpha}(G - v) = \mathrm{\alpha}(G) - 1 [/math].
    По индукции, формула Татта-Берджа содержит [math]G - v[/math] для некоторого множества [math]U'[/math]. Пусть [math]U = U' \bigcup v[/math]. Тогда:
    [math] \mathrm{\alpha}(G) = \mathrm{\alpha}(G - v) + 1 = \dfrac{1}{2}(|V - v|+|U - v| - \mathrm{odd}(G - v - (U - v))) + 1 = [/math]
    [math] = \dfrac{1}{2}(|V| - 1 + |U|- 1 - \mathrm{odd}(G - U)) + 1 = \dfrac{1}{2}(|V|+|U| - \mathrm{odd}(G - U)). [/math]
  2. Для каждой вершины [math]v[/math] есть максимальное паросочетание [math]M[/math] которое не покрывает [math]v[/math] (например [math]C_3[/math])
    Покажем, что существует паросочетание размера [math] \dfrac{1}{2}(|V| - 1) [/math], из которого следует теорема (при [math] U = \emptyset [/math]).
    От противного:
    Предположим что любое максимальная паросочетание [math] M [/math] не покрывает, по крайней мере, две различные вершины [math] u [/math] и [math] v [/math]. Среди всех таких [math] (M, u, v) [/math] выберем их так, что [math] \mathrm{d}(u, u) [/math] в [math] G [/math] — минимально.
    Если [math] \mathrm{d}(u, u) = 1 [/math], то [math] u [/math] и [math] v [/math] являются смежными, и, следовательно, мы можем увеличить [math] M [/math], что противоречит его максимальности.
    Значит [math] \mathrm{d}(u, u) \geqslant 2 [/math], и, следовательно, мы можем выбрать промежуточную вершину [math] t [/math] на пути [math] u-v [/math] и [math] N [/math] максимальное паросочетание, такое что симметрическая разность с [math] M [/math] минимальна. Так как [math] (M, u, v) [/math] минимально, то [math] N [/math] должно охватывать [math] u [/math] и [math] v [/math] так, что есть другая вершина [math] x [/math], покрытая только в [math] M [/math].
    Пусть [math] y [/math] будет вершиной покрытой с [math] x [/math] в [math] M [/math] и заметим [math] y \neq t [/math] (иначе можно было бы добавить к [math] N [/math]). Пусть [math] z [/math] будет вершиной покрытой с [math] y [/math] в [math] N [/math] и заметим [math] z \neq x [/math] (так как [math] x [/math] не покрыто в [math] N [/math]). Тогда [math] N - yz + xy [/math] — паросочетание, которое имеет с [math] M [/math] меньшую симметрическую разность, что противоречит выбору [math] N [/math].
[math]\triangleleft[/math]
Определение:
Множество [math]S \subset V (G)[/math], для которого [math]\mathrm{odd}(G - S) - |S| = \mathrm{def}(G) [/math], называется барьером (англ. barrier).


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


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

Определение:
Структурные единицы декопозиции:
  1. [math]D(G) = \{v \in V \mid [/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] называется фактор-критическим (англ. factor-critical graph), если для любой вершины [math]v \in G[/math] в графе [math]G \setminus {v}[/math] существует совершенное паросочетание.


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


Лемма (Галлаи, о стабильности (англ. stability lemma)):
Пусть [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].

Случай а
Случай b
Случай c
  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] покрывает [math]a[/math], то [math] \alpha (G - a) = \alpha (G) - 1 [/math] и более того, если, для некоторой вершины [math]x \in D(G)[/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[/math] [math] \notin 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[/math] [math] \notin 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] deg_H(v) = 1 [/math] (степень вершины), то [math] P = H(U) [/math] — путь с началом в вершине [math]v[/math]. В пути [math]P[/math] чередуются рёбра из [math] M_w[/math] и [math]M' [/math], причём начинается путь ребром из [math]M_w [/math]. Так как [math] deg_H(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[/math] и [math]E(P)[/math]. то есть, рёбра, входящие ровно в одно из двух множеств). Очевидно, [math]M_v[/math] — максимальное паросочетание графа [math]G[/math], не покрывающее [math]v[/math], поэтому [math] v \in D(G)[/math], противоречие.

b. Путь [math]P[/math] кончается ребром из [math] M_w[/math], вершина [math]a[/math] — конец пути [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. Путь [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]D(G - a) = D(G)[/math], то все вершины, которые были соседями [math]D(G)[/math], таковыми и остались. Однако, по условию [math] a \in A(G)[/math], значит [math]A(G - a) = A(G) \setminus \{a\}[/math].


Так же заметим, что [math]C(G - a) = V(G - a) \setminus (D(G - a) \cup A(G - a)) = V(G - a) \setminus (D(G) \cup (A(G) \setminus \{a\}))[/math][math] = V(G) \setminus (D(G) \cup A(G)) = C(G)[/math]


Наконец, так как [math] a \in A(G)[/math], то все максимальные паросочетания в [math]G[/math] включали [math]a[/math]. Следовательно, [math]\alpha (G - a) \lt \alpha (G)[/math]. Заметим, что, взяв любое максимальное паросочетания в [math]G[/math] и удалив ребро инцидентное [math]a[/math], мы получим паросочетание [math]M'[/math], которое на 1 меньше исходного, при этом [math]M' \in E(G - a)[/math]. В свою очередь, это самое большое паросочетание, которое мы могли теоретически получить в [math]G - a[/math]. Следовательно, [math] \alpha (G - a) = \alpha (G) - 1.[/math]
[math]\triangleleft[/math]


Теорема (Галлаи, Эдмондс):
Пусть [math]G[/math] — граф, [math]U_1\ldots 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\ldots D_n[/math] — фактор-критические.
  3. Любое максимальное паросочетание [math]M[/math] графа [math] G [/math] состоит из совершенного паросочетания графа [math] C [/math], почти совершенных паросочетаний графов [math] D_1\ldots D_n [/math] и покрывает все вершины множества [math] A(G) [/math] рёбрами с концами в различных компонентах связности [math] U_1\ldots U_n. [/math]
  4. [math]\mathrm{def}(G) = n - |A(G)|.[/math]
  5. [math]2\mathrm{\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]. Тем самым, мы доказали пункт [math]1)[/math].
  2. Из формулы [math] \alpha(G - A) = \alpha (G) - |A|[/math] следует, что [math]U_1\ldots 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'| \geqslant |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], то по пунктам [math]1)[/math] и [math]2)[/math] очевидно, что [math]M'[/math] содержит совершенное паросочетание графа [math]C[/math] и почти совершенные паросочетания фактор-критических графов [math]D_1\ldots D_n[/math]. Значит, рёбра паросочетания [math]M[/math] соединяют вершины [math]A[/math] с непокрытыми [math]M'[/math] вершинами различных компонент связности из [math]U_1\ldots U_n[/math].
  4. Из пункта [math]3)[/math] сразу же следуют равенства пункта [math]4)[/math] и [math]5)[/math].
[math]\triangleleft[/math]
Утверждение (следствие из теоремы):
[math]A(G)[/math]барьер графа [math]G[/math]
Лемма (о связи барьера с [math]D(G)[/math]):
Для любого барьера [math]B[/math] графа [math]G[/math] верно, что [math]B\cap D(G) = \varnothing[/math]
Доказательство:
[math]\triangleright[/math]
Рассмотрим [math]U_{1}, U_{2}, \ldots U_{n}[/math] — нечётные компоненты связанности [math]G \setminus B[/math], [math]\ M[/math] — максимальное паросочетание в [math]G[/math]. [math]\forall\ U_{i}\ \exists x \in U_{i}: x[/math] не покрыта [math]\ M[/math] или [math]xv \in M \land v \in B[/math]. Всего графе не покрыто хотя бы [math]odd(G\setminus B) - |B|[/math] вершин. Однако, так как [math]B[/math] — барьер, непокрыто ровно столько вершин. Следовательно, любое максимальное паросочетание не покрывает только вершины из [math]G \setminus B[/math], а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из [math]D(G)[/math] не могла оказаться в барьере.
[math]\triangleleft[/math]
Утверждение (Следствие из леммы):
В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами [math]G \setminus B[/math]
[math]\triangleright[/math]
Так как для барьера [math]B[/math] верно, что [math]odd(G\setminus B) - |B|=def(G) \geqslant 0[/math], то ровно [math]|B|[/math] вершин из нечётных компонент [math]G \setminus B[/math] покрыты рёбрами [math]xv \in M \land v \in B[/math]
[math]\triangleleft[/math]
Лемма (о дополнении барьера):
Пусть [math]x\in A(G)\cup C(G),\ G'=G\setminus x,\ B'[/math] — барьер графа [math]G'[/math]. Тогда [math]B=B'\cup x[/math] — барьер графа [math]G[/math]
Доказательство:
[math]\triangleright[/math]

Так как [math]x \notin D(G)[/math], то для любого максимального паросочетания [math]M: x \in M[/math]. Следовательно, [math]|M'| = |M| - 1[/math], где [math]M'[/math] — максимальное паросочетание в [math]G'[/math].

[math]def(G') = (|V| - 1)- 2 \cdot |M'| = |V| - 2 \cdot |M| + 1 = def(G) + 1[/math]

[math]odd(G - (B'\cup x)) = odd(G' - B') = [/math][math]|B'| + def(G') = |B'| + 1 + def(G) = |B'\cup x| + def(G)[/math]

Отсюда следует, что [math]B[/math] — барьер графа [math]G[/math].
[math]\triangleleft[/math]
Теорема (о структуре барьера):
Любой барьер графа состоит только из вершин [math]A(G)\cup C(G)[/math], причём каждая вершина из этого множества входит в какой-то барьер
Доказательство:
[math]\triangleright[/math]
По лемме о связи барьера с [math]D(G)[/math] мы знаем, что в барьере нет вершин вершин из [math]D(G)[/math]. По лемме о дополнение барьера мы можем взять любую вершину из [math]A(G)\cup C(G)[/math], удалить из графа, и с помощью барьера нового графа получить барьер исходного, включающий данную вершину.
[math]\triangleleft[/math]

См. также

Источники информации