Декомпозиция Эдмондса-Галлаи — различия между версиями
Строка 44: | Строка 44: | ||
}} | }} | ||
{{Определение | {{Определение | ||
− | |id= | + | |id=barrier |
|definition= | |definition= | ||
Множество <tex>S \subset V (G)</tex>, для которого <tex>\mathrm{odd}(G - S) - |S| = \mathrm{def}(G) </tex>, называется '''барьером''' (англ. ''barrier''). | Множество <tex>S \subset V (G)</tex>, для которого <tex>\mathrm{odd}(G - S) - |S| = \mathrm{def}(G) </tex>, называется '''барьером''' (англ. ''barrier''). |
Версия 01:41, 14 декабря 2017
В этом направлении много усилий приложили Вильям Томас Татт (William Thomas Tutte), Клауд Берж (Claude Brege), Джек Эдмондс (Jack Edmonds) и Тибор Галлаи (Tibor Gallai).
Определение: |
Дефицитом (англ. deficit) графа
| мы будем называть величину:
Теорема (Бержа): |
Для любого графа выполняется: |
Теорема (Татта-Бержа): |
Дан граф , размер максимального паросочетания в нем равен: |
Доказательство: |
Предположим
|
Определение: |
Множество | , для которого , называется барьером (англ. barrier).
Определение: |
Пусть | . Множeство соседей (англ. neighbors) определим формулой:
Структурная теорема Эдмондса-Галлаи
Определение: |
Необходимые определения:
|
Определение: |
Граф совершенное паросочетание. | называется фактор-критическим (англ. factor-critical graph), если для любой вершины в графе существует
Теорема (Галлаи): |
— связен и для любой вершины выполняется равенство . |
Лемма (Галлаи, о стабильности (англ. stability lemma)): |
Пусть Тогда:
|
Доказательство: |
Достаточно доказать, что
Предположим, что существует максимальное паросочетание a. Путь b. Путь c. Путь кончается ребром из (см. рисунок) Рассмотрим паросочетание . Тогда , причём . Противоречие с максимальностью паросочетания .Таким образом, наше предположение невозможно и А значит, . . |
Теорема (Галлаи, Эдмондс): |
Пусть — граф, — компоненты связности графа , . Тогда:
|
Доказательство: |
|
Утверждение (следствие из теоремы): |
— барьер графа |