Теорема Татта

Теоре́ма Та́тта про парування дає необхідну і достатню умову на існування досконалого парування у графі. Названа на честь Вільяма Томаса Татта.

Ця теорема узагальнює теорему Холла про одруження для двочасткових графів і є окремим випадком формули Татта — Бержа.

Теорема Татта

Граф, G = (V, E) має досконале парування тоді і тільки тоді, коли для кожного підмножини U у V підграф, індукований V − U, має не більше |U| зв'язкових компонент з непарним числом вершин.

Доведення

Спочатку ми пишемо умову:

$(*)\qquad \forall U\subseteq V,\quad o(G-U)\leq |U|$

де $o(X)$ позначає кількість непарних компонентів підграфа, індукованих $X$.

Необхідність (∗): Розглянемо граф 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, ми визначаємо M₁ як досконале парування в G + xb і M₂ як досконале парування в G + ac. Зверніть увагу на те, що xb ∈ M₁ і ac ∈ M₂.

Припустимо P — максимальний шлях у G який починається з c ребром від M₁ ребра який змінюється між M₁ і M₂. Як може P закінчитися? Якщо лише ми не приїдемо до «спеціальної» вершини, такої як x, a або b, ми завжди можемо продовжити: c це M₂ — збігається з ca, тому перший край P не в M₂, тому друга вершина M₂ — збігається з іншою вершиною, і ми продовжуємо таким чином.

Припустимо, що v позначає останню вершину P. Якщо останній край P знаходиться в M₁, то v має бути a, тому що інакше ми можемо продовжувати з ребра M₂ (навіть, щоб прибути до x або b). У цьому випадку ми визначаємо C:=P + ac. Якщо останній край P знаходиться в M₂, то обов'язково v ∈ {x, b} для аналогічної причини, і ми визначаємо C:=P + va + ac.

Тепер C — це цикл у G + ac парної довжини з кожним іншим ребром в M₂. Тепер ми можемо визначити M := M₂ Δ C (де Δ це симетрична різниця) і ми отримаємо відповідність у G, що є протиріччям.

Див. також

• Теорема Холла
• Парування (теорія графів)
• Теорема Петерсона

Примітки

• 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.