Изменения

Перейти к: навигация, поиск

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

21 398 байт добавлено, 19:35, 4 сентября 2022
м
rollbackEdits.php mass rollback
В этом направлении много усилий приложили Вильям Томас '''Татт''' (''William Thomas Tutte''), Клод '''Берж''' (''Claude Berge''), Джек '''Эдмондс''' (''Jack Edmonds'') и Тибор '''Галлаи''' (''Tibor Gallai'').
{{Определение
|id = deficit
|definition=
'''Дефицитом''' (англ. ''deficit'') графа <tex>G</tex> мы будем называть величину: <br><tex>\mathrm{def}(G) = |V| - 2\alpha (G)</tex>o, <br>где <tex>\alpha (G)</tex> {{---}} размер [[Теорема о максимальном паросочетании и дополняющих цепях#theorem1|максимального паросочетания]] в <tex>G</tex>, а <br><tex>V(G)</tex> {{---U}} множество вершин графа <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-U]: \; (odd(G \setminus S) + |S|) \; \equiv \; n \; (mod \; 2) \;</tex>.}}
{{Теорема
|id = Th_Berge|about=Татта-Бержа
|statement=
дан граф Для любого графа <tex>G</tex> выполняется:<br><tex>\mathrm{def}(G) = \max\limits_{S \subset V(G)} \{\mathrm{odd}(G- S) - |S|\}. </tex>, размер максимального паросочетания в нем |proof= <tex>v\forall S \in V : \; (odd(G\setminus S) + |S|) \; \equiv \; n ( mod \; 2)\;</tex> равен  Рассмотрим несколько случаев:  1. Если <tex>v\max\limits_{S \in V}(odd(G\setminus S) \; - \; |S|) \; = min(U 0 \; </tex>, тогда для любых <tex>S \in V: \; odd(G \setminus S)1\leq |S| \; </tex>, следовательно выполнено условие [[Теорема Татта о существовании полного паросочетания|теоремы Татта]], значит, в графе есть совершенное паросочетание, то есть его дефицит равен нулю.  2. Если <tex> \max\limits_{S \in V}(|V|odd(G \setminus S) -|US|) = k \; </tex>, тогда рассмотрим исходный граф <tex>G</tex> и полный граф <tex>K_k</tex> с <tex>k</tex> вершинами, <tex>W</tex> -oвершины <tex>K_k</tex>. Каждую вершину <tex>K_k</tex> соединим с каждой вершиной <tex>G</tex>. Получим граф <tex>H \; = \; K_k + G \;</tex>, докажем, что для него выполнено условие теоремы Татта. Докажем, что для любых <tex>S \in V_{H}: odd(G-U)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>.
{{Определение
|definition=
множество U, на котором достигается минимум в формуле Татта-Баржа назовем множеством свидетелей.}}
* Если <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|statement) = выполняется следующее:* все k \; </tex>. Таким образом, для графа <tex>H</tex> выполнено условие теоремы Татта, следовательно в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе <tex>H</tex>, удалим вершины <tex>W</tex> из U покрыты любим максимальным паросочетанием в графа <tex>H</tex>. Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин <tex>k</tex>, значит, <tex>def(G* если K - ) \; \leq \; k</tex>. Удалим множество вершин компоненты <tex>A \; = \; arg \max\limits_{S \in V}(odd(H \setminus S) \; - \; |S|) \; </tex> из графа <tex>G-U\;</tex>. Заметим, тогда любое максимальное паросочетание что после удаления в графе осталось <tex>odd(G покрывает как минимум половину вершин в K\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=Татта-Бержа
|statement=
если Дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br><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 = (V, E) называется фактор-критическим</tex>, если в нем нем полного паросочетания, но для каждой вершины v из V граф которого <tex>\mathrm{odd}(G-v имеет полное.}} {{ТеоремаS) - |S|statement=граф \mathrm{def}(G факторо-критический тогда и только тогда) </tex>, когда для каждой вершины v из V существует максимальное паросочетание в G, которое не покрывает вершину vназывается '''барьером''' (англ. ''barrier'').
}}
 {{УтверждениеОпределение|statementdefinition=пусть C - цикл нечетной длины в GПусть <tex>X \subset V </tex>. '''Множeство соседей''' (англ. Если граф G''neighbors'') <tex>X</Сtex> определим формулой: <tex>N(X)= \{ y \in V:(x, полученный сжатием C в одну вершину, фактор-критический, то и G - фактор-критический.y) \in E \}</tex>
}}
=Декомпозиция Эдмондса-Галлаи=
==Структурная теорема Эдмондса-Галлаи==
{{Определение
|neat = 1
|definition=
Структурные единицы декопозиции:
# <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=
необходимые определения:* Граф <tex>D(G) = \{v \in V |</tex> существует максимальное паросочетаниеназывается '''фактор-критическим''' (англ. ''factor-critical graph''), не покрывающее если для любой вершины <tex> v\}</tex>* <tex>A(G) = N(D(in G)) \setminus D(G)</tex>* в графе <tex>C(G) = V \setminus( D(G) \bigcup A(G) )</tex>* <tex> \alpha (G) </tex> - размер максимального паросочетания в <tex>G{v}</tex>существует [[Теорема Холла#def1|совершенное паросочетание]].
}}
{{ЛеммаТеорема|id = theorem_Gallai|about= (Галлаи, о стабильности)
|statement=
пусть <tex> a \in A(G).</tex> Тогда: * {{---}} фактор-критический граф <tex>D(G - a) = D(G)\Leftrightarrow </tex> <br> * <tex>A(G - a) = A(G) \setminus \{a\}</tex>* {{---}} связен и для любой вершины <tex>C(G - a) = Cu \in V(G)</tex> * выполняется равенство <tex> \alpha (G - au) = \alpha (G) - 1.</tex>|proof=много-много и с картинками. :(
}}
 {{ТеоремаЛемма|id = stability_lemma|about= Галлаи, о стабильности (англ. ''stability lemma'')
|statement=
пусть дан граф G = (V, E).<br>тогда:<br>* Пусть <tex> U = a \in A(G) .</tex> - множество свидетелей Татта-БержаТогда: * # <tex>СD(G - a) = D(G) </tex> - объединение всех четных компонент # <tex>A(G - a) = A(G)\setminus \{a\}</tex>* # <tex>DC(G- a) </tex> - объединение всех нечетных компонент <tex>G - A= C(G)</tex>* каждая компонента в # <tex> \alpha (G - Aa) = \alpha (G)- 1.</tex> - фактор-критическая
|proof=
1) Последовательно удаляя вершины множестваДля начала докажем, что <tex> A D(G - a) = AD(G)</tex>. <br>[[Файл: Gallai-lema-a.png|150px|thumb|right|Случай '''а''']][[Файл: Gallai-lema-b.png|150px|thumb|right|Случай '''b''']][[Файл: Gallai-lema-с.png|150px|thumb|right|Случай '''c''']]# Покажем, по лемме о стабильности мы получимчто <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 - Aa) = \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> {{--- A}} максимальное паросочетание графа <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 \Obigcup 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> '''a.''' Путь <tex>P</tex> кончается ребром из <tex> M'</tex> (см. рисунок)<br>Рассмотрим паросочетание <tex>M_v = M_w \oplus E(P)</tex> (симметрическая разность<tex> M_w</tex> и <tex>E(P)</tex>. то есть, рёбра, входящие ровно в одно из двух множеств).* Очевидно, <tex>CM_v</tex> {{---}} максимальное паросочетание графа <tex>G</tex>, не покрывающее <tex>v</tex>, поэтому <tex> v \in D(G )</tex>, противоречие. <br> '''b.''' Путь <tex>P</tex> кончается ребром из <tex> M_w</tex>, вершина <tex>a</tex> {{-- A-}} конец пути <tex>P</tex>. (см.рисунок) <br>Рассмотрим паросочетание <tex>M_v∗ = C(M_w \oplus E(P)) \bigcup \{aw\} </tex>. Тогда <tex> M_v∗ </tex> {{---}} максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> v </tex>, поэтому <tex> v \in D(G)</tex>,противоречие. '''c.''' Путь <tex> P </tex>кончается ребром из <tex> M_w, a \in V(P) </tex> (см. рисунок)* Рассмотрим паросочетание <tex> M'' = M \oplus E(P) </tex>. Тогда <tex> |M''| = |M'| + 1 </tex>, причём <tex>M'' \alpha 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 - Aa) = D(G)</tex>, то все вершины, которые были соседями <tex>D(G)</tex>, таковыми и остались. Однако, по условию <tex> a \alpha in A(G) </tex>, значит <tex>A(G - |a) = A|.(G) \setminus \{a\}</tex>. 
Это означаетТак же заметим, что не существует рёбер, соединяющих вершины из <tex>C(G - Aa) = V(G - a)</tex> и <tex>\setminus (D(G - a) \cup A(G - a)</tex>. Каждое максимальное паросочетание <tex>M'</tex> графа <tex>) = 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>M'</tex> содержитсовершенное паросочетание графа <tex>C</tex>. Тем самым, мы доказали пункт 1).
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> и по теореме 2.12 мы получаем, что граф <tex>Di</tex> - фактор-критический.
3) Пусть M - максимальное паросочетание графа GНаконец, а M' полученоиз M удалением всех рёбер, инцидентных вершинам множества A. Тогда|M'| ≥ |M| − |так как <tex> a \in A| и по формуле α(G − A) = α(G) − |A| понятно</tex>, что M' - максимальноепаросочетание графа то все максимальные паросочетания в <tex>G − A</tex> включали <tex>a</tex>. Более тогоСледовательно, из α<tex>\alpha (G − A- a) = α< \alpha (G) − |A| следует |M'| = |M|−|A|</tex>. Заметим, а значитчто, все вершины множества A покрыты взяв любое максимальное паросочетания в M различными рёбрамию Так как <tex>G</tex> и удалив ребро инцидентное <tex>a</tex>, мы получим паросочетание <tex>M' - максимальное паросочетание графа G - A</tex>, то по пунктам которое на 1) и 2) очевидноменьше исходного, что при этом <tex>M' содержит совершенное паросочетание графа C и почти совершенные паросочетания фактор\in E(G -критических графов D1,..a)</tex>.В свою очередь,Dn. Значитэто самое большое паросочетание, рёбра паросочетания M соединяют вершины A с непокрытыми M' вершинами различных компонентсвязности из U1,..которое мы могли теоретически получить в <tex>G - a</tex>.Следовательно,Un<tex> \alpha (G - a) = \alpha (G) - 1. </tex>4) Из пункта 3) сразу же следуют оба равенства пункта 4}}
{{Теорема
|id = theorem_Gallai_Edmonds
|about = Галлаи, Эдмондс
|statement=
Пусть <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>
# Графы <tex>D_1\ldots D_n</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>
# <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>A = A(G)</tex>, по лемме о стабильности мы получим:
#:* <tex>D(G - A) = D(G),</tex>
#:* <tex>A(G - A) = \O, </tex>
#:* <tex>C(G - A) = C(G),</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>.
}}
|about=следствие из теоремы
|statement=
граф <tex>A(G фактор)</tex> {{-критический тогда и только тогда, когда U не пусто и U - единственное множество свидетелей Татта-Бержа для }} '''барьер''' графа <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> не могла оказаться в барьере.
}}
 
{{Утверждение
|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>
}}
 
{{Лемма
|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>.
}}
 
{{Теорема
|id=barier_struct3
|about=о структуре барьера
|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://immorlica.com/combOpt/lec2.pdf Edmonds-Gallai Decomposition, Edmonds’ Algorithm]
*[https://www.youtube.com/watch?v=1KggxCJZFRg {{---}} Лекция А.С. Станкевича]
 
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Задача о паросочетании]]
Maintenance script
1632
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/34214...85580»

Навигация