37
правок
Изменения
м
правки
{{Определение
|definition=
'''Дефицитом''' (англ. ''deficit'') графа <tex>G</tex> мы будем называть величину: <br>
<tex>\mathrm{def}(G) = |V| - 2\alpha (G)</tex>, <br>
где <tex>\alpha (G)</tex> {{- --}} размер [[Теорема о максимальном паросочетании и дополняющих цепях#theorem1|максимального паросочетания]] в <tex>G</tex>, а <br><tex>V(G)</tex> {{--- }} множество вершин графа <tex>G. </tex>
}}
|statement=
Для любого графа <tex>G</tex> выполняется:<br>
<tex>\mathrm{def}(G) = \max\limits_{S \subset V(G)} \{\mathrm{odd}(G - S) - |S|\}.</tex>
}}
|statement=
Дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br>
<tex>\mathrm{ \alpha} (G) = \min\limits_{U \in V} \{\dfrac{1/}{2}(|V|-|U|-\mathrm{odd}(G-U)\} . </tex>
}}
{{Определение
|definition=
Множество <tex>S \subset V (G)</tex>, для которого <tex>\mathrm{odd}(G - S) - |S| = \mathrm{def}(G) </tex>, называется '''барьером'''(англ. ''barrier'').
}}
{{Определение
Необходимые определения:
[[Файл: EG_red.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены красным]]
# <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> (англ. ''maximum matching in G'')
}}
{{Определение
# Граф <tex>C</tex> имеет совершенное паросочетание.<br>
# Графы <tex>D_1,{...},D_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># <tex>\mathrm{def}(G) = n - |A(G)|, .</tex> <br># <tex>2\mathrm{\alpha}(G) = v(G) + |A(G)| - n</tex>.
|proof=
[[Файл: Edmonds-Gallai_2.png|300px|thumb|right|Пример]]
#:
# Пусть <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>D_1,{...},D_n</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U_1,{...},U_n</tex>.
# Из пункта 3) сразу же следуют оба равенства пункта 4) и 5).
}}
}}
== См. также ==* [[Теорема Татта о существовании полного паросочетания]] == Источники информации==
*[http://www.people.vcu.edu/~dcranston/691/edmonds-gallai.pdf Edmonds-Gallai Decomposition and Factor-Critical Graphs]
*[http://logicimmorlica.pdmi.ras.ru/~dvkcom/211combOpt/graphs_dklec2.pdf Д.В Карпов Edmonds- теория графовGallai Decomposition, Edmonds’ Algorithm]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Задача о паросочетании]]
