Теорема Татта
Теоре́ма Та́тта про парування дає необхідну і достатню умову на існування досконалого парування у графі. Названа на честь Вільяма Томаса Татта.
Ця теорема узагальнює теорему Холла про одруження для двочасткових графів і є окремим випадком формули Татта — Бержа.
Граф, G = (V, E) має досконале парування тоді і тільки тоді, коли для кожного підмножини U у V підграф, індукований V − U, має не більше |U| зв'язкових компонент з непарним числом вершин.[1]
Спочатку ми пишемо умову:
де позначає кількість непарних компонентів підграфа, індукованих .
Необхідність (∗): Розглянемо граф G, з досконалим паруванням. Нехай U буде довільною підмножиною V. Видалимо U. Хай C довільний непарний компонент у G − U. Оскільки G має доскональне парування, принаймні одна вершина у C повинна збігатися з вершиною в U. Отже, кожен непарний компонент має принаймні одну вершину, що збігається з вершиною в U. Оскільки кожна вершина у U може бути в такому відношенні не більш ніж з одним зв'язаним компонентом (через те, що він збігається не більше одного разу у досконалому паруванні) o(G − U) ≤ |U|.
Достатність (∗): Нехай G — довільний граф без досконалого парування. Знайдемо поганий набір вершин S, тобто підмножину V таких, що |S| < o(G − S). Ми можемо припустити, що G є максимум-ребром, тобто, G + e має досконале парування для кожного ребра e не представленого в G. Дійсно, якщо ми знайдемо поганий набір S в графі з максимум-ребром G, тоді S є також набором поганих вершин для кожного підграфа, що він охоплює G, оскільки кожний непарний компонент G − S буде розділений можливо на більше компонентів, принаймні один з яких знову буде непарним.
Ми визначаємо S як сукупність вершин зі ступенем |V| − 1. Спочатку розглянемо випадок, коли всі компоненти G − S є повними графами. Тоді S має бути поганим, оскільки якщо o(G − S) ≤ |S| ми могли б знайти досконале парування, ставлячи одну вершину з кожного непарного компонента з вершиною S і з'єднуючи всі інші вершини (це працюватиме, якщо |V| непарний, але тоді ∅ поганий).
Тепер майте на увазі, що K є компонентом G − S і x, y ∈ K — такі вершини, що xy ∉ E. Нехай x, a, b ∈ K перша вершина найкоротшого x, y — шлях у K. Це гарантує, що xa, ab ∈ E і xb ∉ E. Оскільки a ∉ S, то існує вершина c така, що ac ∉ E. З ребер-максималу G, ми визначаємо M1 як досконале парування в G + xb і M2 як досконале парування в G + ac. Зверніть увагу на те, що xb ∈ M1 і ac ∈ M2.
Припустимо P — максимальний шлях у G який починається з c ребром від M1 ребра який змінюється між M1 і M2. Як може P закінчитися? Якщо лише ми не приїдемо до «спеціальної» вершини, такої як x, a або b, ми завжди можемо продовжити: c це M2 — збігається з ca, тому перший край P не в M2, тому друга вершина M2 — збігається з іншою вершиною, і ми продовжуємо таким чином.
Припустимо, що v позначає останню вершину P. Якщо останній край P знаходиться в M1, то v має бути a, тому що інакше ми можемо продовжувати з ребра M2 (навіть, щоб прибути до x або b). У цьому випадку ми визначаємо C:=P + ac. Якщо останній край P знаходиться в M2, то обов'язково v ∈ {x, b} для аналогічної причини, і ми визначаємо C:=P + va + ac.
Тепер C — це цикл у G + ac парної довжини з кожним іншим ребром в M2. Тепер ми можемо визначити M := M2 Δ C (де Δ це симетрична різниця) і ми отримаємо відповідність у G, що є протиріччям.
- ↑ Lovász та Plummer, (1986), p. 84; Bondy та Murty, (1976), Theorem 5.4, p. 76.
- Bondy, J. A.; Murty, U. S. R. (1976). Graph theory with applications. New York: American Elsevier Pub. Co. ISBN 0-444-19451-7.
- Lovász, László; Plummer, M. D. (1986). Matching theory. Amsterdam: North-Holland. ISBN 0-444-87916-1.