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

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

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

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

Граф, Шаблон:Math має досконале парування тоді і тільки тоді, коли для кожного підмножини Шаблон:Math у Шаблон:Math підграф, індукований Шаблон:Math, має не більше Шаблон:Math зв'язкових компонент з непарним числом вершин.

Доведення

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

$(*)\mathrm{\forall }U\subseteq V,o(G-U)\le |U|$

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

Необхідність (∗): Розглянемо граф Шаблон:Math, з досконалим паруванням. Нехай Шаблон:Math буде довільною підмножиною Шаблон:Math. Видалимо Шаблон:Math. Хай Шаблон:Math довільний непарний компонент у Шаблон:Math. Оскільки Шаблон:Math має доскональне парування, принаймні одна вершина у Шаблон:Math повинна збігатися з вершиною в Шаблон:Math. Отже, кожен непарний компонент має принаймні одну вершину, що збігається з вершиною в Шаблон:Math. Оскільки кожна вершина у Шаблон:Math може бути в такому відношенні не більш ніж з одним зв'язаним компонентом (через те, що він збігається не більше одного разу у досконалому паруванні) Шаблон:Math.

Достатність (∗): Нехай Шаблон:Math — довільний граф без досконалого парування. Знайдемо поганий набір вершин Шаблон:Math, тобто підмножину Шаблон:Math таких, що Шаблон:Math. Ми можемо припустити, що Шаблон:Math є максимум-ребром, тобто, Шаблон:Math має досконале парування для кожного ребра Шаблон:Math не представленого в Шаблон:Math. Дійсно, якщо ми знайдемо поганий набір Шаблон:Math в графі з максимум-ребром Шаблон:Math, тоді Шаблон:Math є також набором поганих вершин для кожного підграфа, що він охоплює Шаблон:Math, оскільки кожний непарний компонент Шаблон:Math буде розділений можливо на більше компонентів, принаймні один з яких знову буде непарним.

Ми визначаємо Шаблон:Math як сукупність вершин зі ступенем Шаблон:Math. Спочатку розглянемо випадок, коли всі компоненти Шаблон:Math є повними графами. Тоді Шаблон:Math має бути поганим, оскільки якщо Шаблон:Math ми могли б знайти досконале парування, ставлячи одну вершину з кожного непарного компонента з вершиною Шаблон:Math і з'єднуючи всі інші вершини (це працюватиме, якщо Шаблон:Math непарний, але тоді Шаблон:Math поганий).

Тепер майте на увазі, що Шаблон:Math є компонентом Шаблон:Math і Шаблон:Math — такі вершини, що Шаблон:Math. Нехай Шаблон:Math перша вершина найкоротшого Шаблон:Math — шлях у Шаблон:Math. Це гарантує, що Шаблон:Math і Шаблон:Math. Оскільки Шаблон:Math, то існує вершина Шаблон:Math така, що Шаблон:Math. З ребер-максималу Шаблон:Math, ми визначаємо Шаблон:Math як досконале парування в Шаблон:Math і Шаблон:Math як досконале парування в Шаблон:Math. Зверніть увагу на те, що Шаблон:Math і Шаблон:Math.

Припустимо Шаблон:Math — максимальний шлях у Шаблон:Math який починається з Шаблон:Math ребром від Шаблон:Math ребра який змінюється між Шаблон:Math і Шаблон:Math. Як може Шаблон:Math закінчитися? Якщо лише ми не приїдемо до «спеціальної» вершини, такої як Шаблон:Math або Шаблон:Math, ми завжди можемо продовжити: Шаблон:Math це Шаблон:Math — збігається з Шаблон:Math, тому перший край Шаблон:Math не в Шаблон:Math, тому друга вершина Шаблон:Math — збігається з іншою вершиною, і ми продовжуємо таким чином.

Припустимо, що Шаблон:Math позначає останню вершину Шаблон:Math. Якщо останній край Шаблон:Math знаходиться в Шаблон:Math, то Шаблон:Math має бути Шаблон:Math, тому що інакше ми можемо продовжувати з ребра Шаблон:Math (навіть, щоб прибути до Шаблон:Math або Шаблон:Math). У цьому випадку ми визначаємо Шаблон:Math. Якщо останній край Шаблон:Math знаходиться в Шаблон:Math, то обов'язково Шаблон:Math} для аналогічної причини, і ми визначаємо Шаблон:Math.

Тепер Шаблон:Math — це цикл у Шаблон:Math парної довжини з кожним іншим ребром в Шаблон:Math. Тепер ми можемо визначити Шаблон:Math (де Шаблон:Math це симетрична різниця) і ми отримаємо відповідність у Шаблон:Math, що є протиріччям.

Див. також

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

Посилання

• Шаблон:Cite book
• Шаблон:Cite book