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

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

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

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

$\frac{1}{2}\underset{U\subseteq V}{\min }(|U|-\mathrm{odd}(G-U)+|V|)$ ,

де $\mathrm{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. Тобто, найбільше парування є досконалим і теорему Татта можна отримати як наслідок формули Татта — Бержа, а саму формулу можна вважати узагальненням теореми Татта.

Література

• Шаблон:Книга Репринт Dover Publications, 2001.
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга Архивная копия от 13 апреля 2010 на Wayback Machine
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Посилання

• Шаблон:Стаття
• Шаблон:Стаття