Декомпозиция Эдмондса-Галлаи — различия между версиями
Dogzik (обсуждение | вклад) |
Dogzik (обсуждение | вклад) |
||
Строка 128: | Строка 128: | ||
#:* <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>. Тем самым, мы доказали пункт 1). | + | #:Это означает, что не существует рёбер, соединяющих вершины из <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> \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>, то по пунктам 1) и 2) очевидно, что <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>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>. |
− | # Из пункта 3) сразу же следуют равенства пункта 4) и 5). | + | # Из пункта <tex>3)</tex> сразу же следуют равенства пункта <tex>4)</tex> и <tex>5)</tex>. |
}} | }} | ||
Версия 02:06, 15 декабря 2017
В этом направлении много усилий приложили Вильям Томас Татт (William Thomas Tutte), Клауд Берж (Claude Brege), Джек Эдмондс (Jack Edmonds) и Тибор Галлаи (Tibor Gallai).
Определение: |
Дефицитом (англ. deficit) графа
| мы будем называть величину:
Теорема (Бержа): |
Для любого графа выполняется: |
Теорема (Татта-Бержа): |
Дан граф , размер максимального паросочетания в нем равен: |
Доказательство: |
Предположим
|
Определение: |
Множество | , для которого , называется барьером (англ. barrier).
Определение: |
Пусть | . Множeство соседей (англ. neighbors) определим формулой:
Структурная теорема Эдмондса-Галлаи
- максимальное паросочетание, не покрывающее существует
- — размер максимального паросочетания в
Определение: |
Граф совершенное паросочетание. | называется фактор-критическим (англ. factor-critical graph), если для любой вершины в графе существует
Теорема (Галлаи): |
— связен и для любой вершины выполняется равенство . |
Лемма (Галлаи, о стабильности (англ. stability lemma)): |
Пусть Тогда:
|
Доказательство: |
Достаточно доказать, что
Предположим, что существует максимальное паросочетание a. Путь b. Путь c. Путь кончается ребром из (см. рисунок) Рассмотрим паросочетание . Тогда , причём . Противоречие с максимальностью паросочетания .Таким образом, наше предположение невозможно и А значит, . . |
Теорема (Галлаи, Эдмондс): |
Пусть — граф, — компоненты связности графа , . Тогда:
|
Доказательство: |
|
Утверждение (следствие из теоремы): |
— барьер графа |
Лемма (о связи барьера с | ):
Для любого барьера графа верно, что |
Доказательство: |
Рассмотрим | — нечётные компоненты связанности , — максимальное паросочетание в . не покрыта или . Всего графе не покрыто хотя бы вершин. Однако так как — барьер, непокрыто ровно столько вершин. Следовательно любое максимальное паросочетание не покрывает только вершины из , а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из не могла оказаться в барьере.
Утверждение (Следствие из леммы): |
В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами |
Так как в барьере | , то ровно вершин из нечётных компонент покрыты рёбрами
Лемма (о дополнении барьера): |
Пусть — барьер графа . Тогда — барьер графа |
Доказательство: |
Так как , то — максимального паросочетания в . Следовательно , где — максимальное паросочетание в .
Отсюда следует, что — барьер графа . |
Теорема (о структуре барьера): |
Любой барьер графа состоит только из вершин , причём каждая вершина из этого множества входит в какой-то барьер |
Доказательство: |
По лемме о связи барьера с | мы знаем, что в барьере нет вершин вершин из . По лемме о дополнение барьера мы можем взять любую вершину из , удалить из графа, и с помощью барьера нового графа получить барьер исходного, включающий данную вершину.