![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/58/Class-2-planar-3-regular.svg/220px-Class-2-planar-3-regular.svg.png)
Формула Татта — Бержа — в теорії графів формула, що визначає розмір найбільшого парування в графі. Є узагальненням теореми Татта про парування. Встановив та довів Клод Берж[en].
Теорема стверджує, що розмір найбільшого парування в графі дорівнює:
- ,
де — число зв'язних компонент графа , що мають непарне число вершин.
Пояснення
Інтуїтивно зрозуміло, що для будь-якої підмножини вершин єдиний спосіб повністю покрити компоненту з непарним числом вершин — вибрати в парування ребро, що з'єднує одну з вершин з . Якщо в компоненті з непарним числом вершин такого ребра в паруванні немає, частина парування покриє вершини компоненти, але, оскільки число вершин непарне, принаймні одна вершина залишиться непокритою. Таким чином, якщо деяка підмножина вершин має малий розмір, але при її видаленні створюється багато непарних компонент, то залишиться багато непокритих пароуванням вершин, з чого випливає, що й парування буде малим. Це міркування можна зробити строгим, якщо взяти до уваги, що розмір найбільшого парування не перевищує значення, яке дає формула Татта — Бержа.
Формула показує, що це обмеження є єдиною перешкодою для отримання більшого парування — розмір оптимального парування визначається підмножиною , що має найбільшу різницю між числом непарних компонент поза і числом вершин в . Тобто завжди існує точна підмножина , видалення якої створює правильне число непарних компонент, що задовольняють формулі. Один зі способів отримати таку множину — вибрати будь-яке найбільше парування та включити в вершини, які або не покриті паруванням , або досяжні з непокритої вершини чергованим ланцюгом[1], який завершується ребром з парування. Визначивши як множину вершин, які з'єднуються паруванням з вершинами з , виходить, що ніякі дві вершини з не можуть бути суміжними, інакше можна з'єднати дві непокриті вершини чергованим шляхом, що суперечить максимальності [2]. Будь-який сусід вершини із має належати , в іншому випадку ми можемо розширити чергований шлях до на пару ребер до сусідів, внаслідок чого сусіди стають частиною . Отже, в будь-яка вершина утворює компоненту з однієї вершини, тобто має непарну кількість вершин. Не може бути інших непарних компонент, оскільки після видалення всі інші вершини залишаються покритими паруванням.
Зв'язок із теоремою Татта
Теорема Татта про парування описує графи з досконалими паруваннями як графи, для яких видалення будь-якої підмножини вершин створює максимум непарних компонентів. (Підмножину , яка містить принаймні непарних компонентів, можна завжди знайти у вигляді порожньої множини). У цьому випадку за формулою Татта — Бержа розмір парування дорівнює /2. Тобто, найбільше парування є досконалим і теорему Татта можна отримати як наслідок формули Татта — Бержа, а саму формулу можна вважати узагальненням теореми Татта.
Примітки
- ↑ Чергований шлях — це шлях, у якому чергуються ребра з парування і такі, що не входять у парування (Берж, 1962)
- ↑ Теорема: Парування графа є найбільшим тоді й лише тоді, коли не існує чергованого ланцюга, що з'єднує два різні непокриті паруванням вершини. (Берж, 1962)
Література
- C. Berge[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) — 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[en]. 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: .