Теоре́ма Та́тта про парування дає необхідну і достатню умову на існування досконалого парування у графі. Названа на честь Вільяма Томаса Татта.
Ця теорема узагальнює теорему Холла про одруження для двочасткових графів і є окремим випадком формули Татта — Бержа.
Теорема Татта Граф, має досконале парування тоді і тільки тоді, коли для кожного підмножини у підграф, індукований , має не більше зв'язкових компонент з непарним числом вершин., p. 84; , Theorem 5.4, p. 76.
Доведення Спочатку ми пишемо умову:
де позначає кількість непарних компонентів підграфа, індукованих .
Необхідність (∗): Розглянемо граф , з досконалим паруванням. Нехай буде довільною підмножиною . Видалимо . Хай довільний непарний компонент у . Оскільки має доскональне парування, принаймні одна вершина у повинна збігатися з вершиною в . Отже, кожен непарний компонент має принаймні одну вершину, що збігається з вершиною в . Оскільки кожна вершина у може бути в такому відношенні не більш ніж з одним зв'язаним компонентом (через те, що він збігається не більше одного разу у досконалому паруванні) .
Достатність (∗): Нехай — довільний граф без досконалого парування. Знайдемо поганий набір вершин , тобто підмножину таких, що . Ми можемо припустити, що є максимум-ребром, тобто, має досконале парування для кожного ребра не представленого в . Дійсно, якщо ми знайдемо поганий набір в графі з максимум-ребром , тоді є також набором поганих вершин для кожного підграфа, що він охоплює , оскільки кожний непарний компонент буде розділений можливо на більше компонентів, принаймні один з яких знову буде непарним.
Ми визначаємо як сукупність вершин зі ступенем . Спочатку розглянемо випадок, коли всі компоненти є повними графами. Тоді має бути поганим, оскільки якщо ми могли б знайти досконале парування, ставлячи одну вершину з кожного непарного компонента з вершиною і з'єднуючи всі інші вершини (це працюватиме, якщо непарний, але тоді поганий).
Тепер майте на увазі, що є компонентом і — такі вершини, що . Нехай перша вершина найкоротшого — шлях у . Це гарантує, що і . Оскільки , то існує вершина така, що . З ребер-максималу , ми визначаємо як досконале парування в і як досконале парування в . Зверніть увагу на те, що і .
Припустимо — максимальний шлях у який починається з ребром від ребра який змінюється між і . Як може закінчитися? Якщо лише ми не приїдемо до «спеціальної» вершини, такої як або , ми завжди можемо продовжити: це — збігається з , тому перший край не в , тому друга вершина — збігається з іншою вершиною, і ми продовжуємо таким чином.
Припустимо, що позначає останню вершину . Якщо останній край знаходиться в , то має бути , тому що інакше ми можемо продовжувати з ребра (навіть, щоб прибути до або ). У цьому випадку ми визначаємо . Якщо останній край знаходиться в , то обов'язково } для аналогічної причини, і ми визначаємо .
Тепер — це цикл у парної довжини з кожним іншим ребром в . Тепер ми можемо визначити (де це симетрична різниця) і ми отримаємо відповідність у , що є протиріччям.
Див. також Теорема Холла Парування (теорія графів) Теорема Петерсона
Примітки
Джерела