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

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

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

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

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

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

Пояснення

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

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

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

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

Примітки

1. Чергований шлях — це шлях, у якому чергуються ребра з парування і такі, що не входять у парування (Берж, 1962)
2. Теорема: Парування графа є найбільшим тоді й лише тоді, коли не існує чергованого ланцюга, що з'єднує два різні непокриті паруванням вершини. (Берж, 1962)

Література

• ^[en]. 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) — .
• J. A. Bondy, U. S. R. Murty. Exercise 5.3.4, p. 80 // . — New York : North Holland, 1976. — . Архивная копия от 13 апреля 2010 на Wayback Machine
• Richard A. Brualdi. Combinatorial matrix classes. — Cambridge : Cambridge University Press, 2006. — Т. 108. — С. 360. — (Encyclopedia of Mathematics and Its Applications) — .
• László Lovász, M. D. Plummer. Matching theory. — Amsterdam : North-Holland, 1986. — С. 90—91. — .
• . Combinatorial optimization: polyhedra and efficiency. — Springer-Verlag, 2003. — С. 413. — .

Посилання

• ^[en]. Sur le couplage maximum d'un graphe // . — 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.