Изменения

'''Дефицитом''' (англ. ''deficit'') графа <tex>G</tex> мы будем называть величину: <br><tex>o\mathrm{def}(G) = |V| -U2\alpha (G)</tex> , <br>где <tex>\alpha (G)</tex> {{- количество компонент связности нечетного размера --}} размер [[Теорема о максимальном паросочетании и дополняющих цепях#theorem1|максимального паросочетания]] в <tex> G[</tex>, а <br><tex>V(G)</tex> {{--U]-}} множество вершин графа <tex>G. </tex>.}}

|id = Th_Berge|about=Татта-Бержа

дан граф Для любого графа <tex>G</tex>, размер максимального паросочетания в нем выполняется:<texbr>v(G)</tex> равен:<tex>v\mathrm{def}(G) = min\max\limits_{S \subset V(U in VG)1/2} \{\mathrm{odd}(|V|G - S) -|US|-o(G-U)) \}. </tex>

множество UМножество <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=Структурные единицы декопозиции:# <tex>D(G) = \{v \in V \mid </tex> существует [[Теорема о максимальном паросочетании и дополняющих цепях|statementмаксимальное паросочетание]], не покрывающее <tex> v\}</tex># <tex>A(G) = N(D(G)) \setminus D(G)</tex># <tex>C(G) =V \setminus(D(G) \bigcup A(G))</tex>если U # <tex> \alpha (G) </tex> {{-- не пустое множество свидетелей Татта-Бержа для графа G, тогда }} размер максимального паросочетания в <tex> G есть вершины, которые входят в любое максимальное паросочетание.</tex>

граф Граф <tex>G = (V, E) </tex> называется '''фактор-критическим''' (англ. ''factor-critical graph''), если в нем нем полного паросочетания, но для каждой любой вершины <tex>v из V граф \in G</tex> в графе <tex>G-\setminus {v имеет полное}</tex> существует [[Теорема Холла#def1|совершенное паросочетание]].}}

<tex>G</tex> {{---}} фактор-критический граф <tex> \Leftrightarrow </tex> <br><tex>G факторо</tex> {{--критический тогда -}} связен и только тогда, когда для каждой любой вершины v из <tex>u \in V существует максимальное паросочетание в (G) </tex> выполняется равенство <tex> \alpha (G - u) = \alpha (G, которое не покрывает вершину v)</tex>.

 {{УтверждениеЛемма|id = stability_lemma|about= Галлаи, о стабильности (англ. ''stability lemma'')

пусть Пусть <tex> a \in A(G).</tex> Тогда: # <tex>D(G - a) = D(G)</tex> # <tex>A(G - a) = A(G) \setminus \{a\}</tex># <tex>C(G - a) = C (G)</tex> # <tex> \alpha (G - a) = \alpha (G) - 1.</tex>|proof=Для начала докажем, что <tex>D(G - a) = D(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 - 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> {{---}} очевидно, полученный сжатием C он является объединением нескольких путей и чётных циклов. Пусть <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>M_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> {{---}} конец пути <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>, противоречие. '''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'' \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>

{{Определение |definition=необходимые определения:* Наконец, так как <tex>Da \in A(G) = \{v \in V |</tex> существует максимальное паросочетание, не покрывающее то все максимальные паросочетания в <tex> v\}G</tex> включали <tex>a</tex>* . Следовательно, <tex>A\alpha (G- a) = N(D(G)) < \setminus Dalpha (G)</tex>* . Заметим, что, взяв любое максимальное паросочетания в <tex>C(G) = V </tex> и удалив ребро инцидентное <tex>a</tex>, мы получим паросочетание <tex>M'</tex>, которое на 1 меньше исходного, при этом <tex>M' \setminus( Din E(G) \bigcup A(G) - a)</tex>* . В свою очередь, это самое большое паросочетание, которое мы могли теоретически получить в <tex> \alpha (G) - a</tex> - размер максимального паросочетания в . Следовательно, <tex>\alpha (G - a) = \alpha (G) - 1.</tex>

 {{ЛеммаТеорема|id = theorem_Gallai_Edmonds|about= (Галлаи, о стабильности) Эдмондс

пусть Пусть <tex> a G</tex> {{---}} граф, <tex>U_1\in Aldots U_n</tex> {{---}} компоненты связности графа <tex>G(D(G).)</tex> Тогда: * , <tex>DD_i = G(G - aU_i) , C = DG(C(G))</tex>. Тогда:# Граф <tex>C</tex> имеет совершенное паросочетание.<br># Графы <tex>D_1\ldots D_n</tex> {{---}} фактор-критические. <br> * # Любое максимальное паросочетание <tex>M</tex> графа <tex>A(G - a) = </tex> состоит из совершенного паросочетания графа <tex> C </tex>, почти совершенных паросочетаний графов <tex> D_1\ldots D_n </tex> и покрывает все вершины множества <tex> A(G) </tex> рёбрами с концами в различных компонентах связности <tex> U_1\setminus \{a\}ldots U_n. </tex> <br>* # <tex>C\mathrm{def}(G - a) = Cn - |A(G)|.</tex> <br> * # <tex> 2\mathrm{\alpha }(G - a) = \alpha v(G) + |A(G) | - 1.n</tex>.

много[[Файл: 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=следствие из теоремы

пусть дан граф G = (V, E).<br>тогда:<br>* <tex> U = A(G) </tex> {{- множество свидетелей Татта-Бержа* -}} '''барьер''' графа <tex>С(G) </tex> - объединение всех четных компонент }} {{Лемма|id = barier_struct1|about = о связи барьера с <tex>G - AD(G)</tex>* |statement= Для любого барьера <tex>D(G) B</tex> - объединение всех нечетных компонент графа <tex>G - A(G)</tex>* каждая компонента в верно, что <tex> G - AB\cap D(G)= \varnothing</tex> - фактор-критическая|proof= Рассмотрим <tex>U_{1) A Последовательно удаляя вершины множества A = A(G)D по лемме о стабильности мы получимD(G − A) = D(G)}, A(G − A) = ∅U_{2}, C( \ldots U_{n}</tex> {{---}} нечётные компоненты связанности <tex>G − A) = C(G)\setminus B</tex>,α(<tex>\ M</tex> {{---}} максимальное паросочетание в <tex>G − A) = α</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) − - |AB|</tex> вершин.Это означаетОднако, так как <tex>B</tex> {{---}} барьер, что не существует рјберD соединяющих вершины из C(G − A) и D(G − A)непокрыто '''ровно''' столько вершин. Каждое Следовательно, любое максимальное паросочетание M' графа G - A не покрывает все только вершины множества C(из <tex>G)\setminus B</tex>, поэтому M' содержитсовершенное паросочетание графа Cа значит каждая вершина барьера покрыта в любом максимальном паросочетании. Тем самымОтсюда получаем, мы доказали пункт 1что ни одна вершина из <tex>D(G)</tex> не могла оказаться в барьере.}}

2) Из формулы α{{Утверждение|id = barier_struct1a|about=Следствие из леммы|statement=В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами <tex>G \setminus B</tex>|proof=Так как для барьера <tex>B</tex> верно, что <tex>odd(G − A\setminus B) - |B|= αdef(G) − \geqslant 0</tex>, то ровно <tex>|AB|. следуетD что U1,..,Un- компоненты связности графа </tex> вершин из нечётных компонент <tex>G − A. Для любой вершины u \setminus B</tex> покрыты рёбрами <tex>xv \in M \land v \in Ui существует максимальноеB</tex>}}

паросочетание Mu графа {{Лемма|id = barier_struct2|about = о дополнении барьера|statement= Пусть <tex>x\in A(G)\cup C(G),\ G'=G \setminus x,\ B'</tex> {{-- A, не содержащее u. Так как Ui - компонента связности }} барьер графа <tex>G '</tex>. Тогда <tex>B=B'\cup x</tex> {{--- A, паросочетание Mu содержит максимальное паросочетание }} барьер графа Di <tex>G</tex>|proof= Так как <tex>x \notin D(разумеетсяD не покрывающее вершину uG)</tex>, то для любого максимального паросочетания <tex>M: x \in M</tex>. Следовательно, α(Di) <tex>|M'| = α(Di |M| - u) и по теореме 2.12 мы получаем1</tex>, что граф Di где <tex>M'</tex> {{- фактор-критический-}} максимальное паросочетание в <tex>G'</tex>.

3) Пусть M - максимальное паросочетание графа <tex>def(G, а M' полученоиз M удалением всех рёбер, инцидентных вершинам множества A. Тогда|M'| ≥ |M| − |A| и по формуле α(G − A) = α(G) − |AV| понятно, что M' - максимальноепаросочетание графа G − A. Более того, из α(G − A1) = α(G) − |A| следует - 2 \cdot |M'| = |MV|−- 2 \cdot |AM|, а значит, все вершины множества A покрыты в M различными рёбрамию Так как M' - максимальное паросочетание графа + 1 = def(G - A, то по пунктам ) + 1) и 2) очевидно, что M' содержит совершенное паросочетание графа C и почти совершенные паросочетания фактор-критических графов D1,...,Dn. Значит, рёбра паросочетания M соединяют вершины A с непокрытыми M' вершинами различных компонентсвязности из U1,...,Un. 4) Из пункта 3) сразу же следуют оба равенства пункта 4</tex>

{{Утверждение== См. также ==* [[Теорема Татта о существовании полного паросочетания]]* [[Лапы и минимальные по включению барьеры в графе]]* [[Пересечение всех максимальных по включению барьеров]] |about=следствие из теоремы= Источники информации==|statement=*[http://www.people.vcu.edu/~dcranston/691/edmonds-gallai.pdf Edmonds-Gallai Decomposition and Factor-Critical Graphs]граф G фактор*[http://immorlica.com/combOpt/lec2.pdf Edmonds-критический тогда и только тогдаGallai Decomposition, когда U не пусто Edmonds’ Algorithm] [[Категория:Алгоритмы и U - единственное множество свидетелей Татта-Бержа для Gструктуры данных]]}}[[Категория:Задача о паросочетании]]