Формула Татта — Бержа

У цьому графі видалення однієї вершини в центрі дає три непарні компоненти, три підграфи по п'ять вершин. Таким чином, за формулою Татта — Бержа граф має не більше (1−3+16)/2 = 7 ребер у будь-якому паруванні.

Формула Татта — Бержа — в теорії графів формула, що визначає розмір найбільшого парування в графі. Є узагальненням теореми Татта про парування. Встановив та довів Клод Берж.

Теорема стверджує, що розмір найбільшого парування в графі $G=(V,E)$ дорівнює:

${\frac {1}{2}}\min _{U\subseteq V}\left(|U|-\operatorname {odd} (G-U)+|V|\right)$ ,

де $\operatorname {odd} (H)$ — число зв'язних компонент графа $H$, що мають непарне число вершин.

Пояснення

Інтуїтивно зрозуміло, що для будь-якої підмножини вершин $U$ єдиний спосіб повністю покрити компоненту $G-U$ з непарним числом вершин — вибрати в парування ребро, що з'єднує одну з вершин $G-U$ з $U$. Якщо в компоненті з непарним числом вершин такого ребра в паруванні немає, частина парування покриє вершини компоненти, але, оскільки число вершин непарне, принаймні одна вершина залишиться непокритою. Таким чином, якщо деяка підмножина вершин $U$ має малий розмір, але при її видаленні створюється багато непарних компонент, то залишиться багато непокритих пароуванням вершин, з чого випливає, що й парування буде малим. Це міркування можна зробити строгим, якщо взяти до уваги, що розмір найбільшого парування не перевищує значення, яке дає формула Татта — Бержа.

Формула показує, що це обмеження є єдиною перешкодою для отримання більшого парування — розмір оптимального парування визначається підмножиною $U$, що має найбільшу різницю між числом непарних компонент поза $U$ і числом вершин в $U$. Тобто завжди існує точна підмножина $U$, видалення якої створює правильне число непарних компонент, що задовольняють формулі. Один зі способів отримати таку множину $U$ — вибрати будь-яке найбільше парування $M$ та включити в $X$ вершини, які або не покриті паруванням $M$, або досяжні з непокритої вершини чергованим ланцюгом, який завершується ребром з парування. Визначивши $U$ як множину вершин, які з'єднуються паруванням $M$ з вершинами з $X$, виходить, що ніякі дві вершини з $X$ не можуть бути суміжними, інакше можна з'єднати дві непокриті вершини чергованим шляхом, що суперечить максимальності $M$. Будь-який сусід вершини $x$ із $X$ має належати $U$, в іншому випадку ми можемо розширити чергований шлях до $x$ на пару ребер до сусідів, внаслідок чого сусіди стають частиною $U$. Отже, в $G-U$ будь-яка вершина $X$ утворює компоненту з однієї вершини, тобто має непарну кількість вершин. Не може бути інших непарних компонент, оскільки після видалення $U$ всі інші вершини залишаються покритими паруванням.

Зв'язок із теоремою Татта

Теорема Татта про парування описує графи з досконалими паруваннями як графи, для яких видалення будь-якої підмножини $U$ вершин створює максимум $|U|$ непарних компонентів. (Підмножину $U$, яка містить принаймні $|U|$ непарних компонентів, можна завжди знайти у вигляді порожньої множини). У цьому випадку за формулою Татта — Бержа розмір парування дорівнює $|V|$/2. Тобто, найбільше парування є досконалим і теорему Татта можна отримати як наслідок формули Татта — Бержа, а саму формулу можна вважати узагальненням теореми Татта.

Література

• C. Berge. The Theory of Graphs. — Methuen, 1962. Репринт Dover Publications, 2001.
• К. Берж. Теория графов и её применение. — Москва : Издательство иностранной литературы, 1962.
• J. A. Bondy, U. S. R. Murty. Graph theory: an advanced course. — Springer-Verlag, 2007. — С. 428. — (Graduate Texts in Mathematics) — ISBN 1-84628-969-6.
• J. A. Bondy, U. S. R. Murty. Exercise 5.3.4, p. 80 // Graph Theory with Applications. — New York : North Holland, 1976. — ISBN 0-444-19451-7. Архивная копия от 13 апреля 2010 на Wayback Machine
• Richard A. Brualdi. Combinatorial matrix classes. — Cambridge : Cambridge University Press, 2006. — Т. 108. — С. 360. — (Encyclopedia of Mathematics and Its Applications) — ISBN 0-521-86565-4.
• László Lovász, M. D. Plummer. Matching theory. — Amsterdam : North-Holland, 1986. — С. 90—91. — ISBN 0-444-87916-1.
• Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency. — Springer-Verlag, 2003. — С. 413. — ISBN 3-540-44389-4.

Посилання

• C. Berge. Sur le couplage maximum d'un graphe // Comptes rendus hebdomadaires des séances de l'Académie des sciences. — 1958. — Т. 247. — С. 258—259.
• W. T. Tutte. The factorization of linear graphs // The Journal of the London Mathematical Society, Ser. 1. — 1947. — Т. 22, вип. 2. — С. 107—111. — DOI:10.1112/jlms/s1-22.2.107.