Теорема Кеніга (комбінаторика)

Теорема названа на честь угорського математика Денеша Кеніга. Кеніг заявив про неї в 1914 і опублікував в 1916 доказ, що будь-який регулярний дводольний граф має зроблене парування, і, узагальнено, що хроматичний індекс будь-якого двудольного графу (тобто мінімальне число паросполучень, на які можна розкласти всі дуги графу) дорівнює максимальному ступені[1]. Останнє твердження відоме як теорема Кеніга про реберне розфарбування.[2] Однак Бонді і Мерфі (Bondy, Murty, 1976) приписують саму теорему більш пізній роботі Кеніга (1931). Згідно Бигу (Bigg) Кеніг приписує ідею вивчення парування в дводольних графах своєму батькові, математику Юлію Кенігу .

Граф називається дводольним, якщо його вершини можна розбити на дві множини так, що у кожного ребра кінцеві вершини належать різним множинам. Вершинне покриття  — це множина вершин, така, що будь-яке ребро графу має хоча б одну кінцеву вершину з цієї множини. Вершинне покриття називається мінімальним, якщо ніяке інше вершинне покриття не має меншого числа вершин.

Теорема Кеніга стверджує, що в будь-якому двочастковому графі число ребер у максимальному паруванні дорівнює числу вершин у мінімальному вершинному покритті.

Для графів, які не є дводольними, ситуація із завданнями про максимальне парування і мінімальне вершинне покриття зовсім інша — максимальне парування можна знайти за поліноміальний час для будь-якого графу, в той час як пошук мінімального вершинного покриття є NP-повним завданням. Доповнення вершинного покриття для будь-якого графу — це незалежна множина і пошук максимальної незалежної множини — це ще одна NP-повна задача. Еквівалентність між паруванням і покриттями, виражена в теоремі Кеніга, дозволяє знайти мінімальне вершинне покриття і максимальну незалежну множину за поліноміальний час для двочасткових графів всупереч NP-повноті цієї задачі для більш загальних сімейств графів.

Теорема Кеніга еквівалентна масі інших мінімаксних теорем в теорії графів і комбінаториці, таких як теорема Холла про весілля і теорема Ділуорса. Оскільки парування в двочасткових графах є окремим випадком теореми Форда - Фалкерсона, теорема Кеніга випливає з теореми Форда — Фалкерсона.

У будь-якому дводольному графі число ребер в максимальному паруванні дорівнює числу вершин у мінімальному вершинному покритті.

У російськомовному Інтернеті розповсюджене наступне формулювання теореми: Якщо прямокутна матриця складена з нулів і одиниць, то мінімальне число ліній, що містять всі одиниці, дорівнює максимальному числу одиниць, які можуть бути обрані так, щоб ніякі дві з них не лежали на одній і тій же лінії (термін «лінія» позначає або рядок, або стовпець у матриці).

Дане формулювання легко перекладається на мову дводольних графів: Рядки таблиці — це вершини однієї частини дводольного графу, стовпці — іншої частини.

Лінії — це верхове покриття.

Одиниці матриці — ребра. Вимога, щоб ніякі дві одиниці не лежали на одній лінії, відповідає паруванню.

Дводольний граф на малюнку вгорі має 14 вершин, Парування з 6 ребрами виділено синім кольором, а верхове покриття з шести вершин виділено червоним. Немає меншого за розміром верхового покриття, оскільки будь-яка вершина повинна включати щонайменше одну кінцеву вершину ребра паросполучення, так що це покриття мінімальне. Таким же чином, немає паросполучення більшого розміру, оскільки будь-яке ребро в паросполученні повинно містити, щонайменше, одну кінцеву вершину з верхового покриття, так що це паросполучення максимальне. Теорема Кеніга якраз і стверджує рівність розмірів паросполучення і покриття (в даному прикладі обидва числа дорівнюють шести).

Розділення вершин двудольного графу з паросполучення на парні і непарні рівні для доведення теореми Кеніга.

Нехай заданий дводольний граф G = (V, E), і нехай V ділиться на ліву множину L і праву R. Нехай M — максимальне паросполучення в G.

За визначенням «паросполучення», ніяка вершина не може належати більш ніж одному ребру з M. Таким чином, якщо верхове покриття з |M| вершинами може бути побудовано, воно мінімально.

Якщо M — досконале паросполучення (що передбачає, що M — максимально), то |L| = |R| = |M|. Оскільки кожне ребро G пов'язане рівно з однією вершиною з L і рівно з однією вершиною з R, або L, або R є верховим покриттям розміру |M| і теорема доведена.

В іншому випадку використовуємо побудову шляху, який чергується для побудови мінімального покриття. При заданому M перемежовуючим шляхом називається шлях, ребра якого по черзі беруться з M і E \ M. Розділимо вершини V графу G на підмножини S_i, як описано нижче. Ми покажемо, що об'єднання підмножин з непарними індексами є верховим покриттям з |M| вершинами.

• Нехай S₀ складається з усіх вершин, які не належать паросполученням з M.
• Для цілого j ≥ 0, нехай S_2j+1 — множина всіх вершин v, таких, що

1. v з деякою вершиною з S_2j ребром з E \ M
2. v входить ні в одну з раніше побудованих множин S_k, де k < 2j+1.

Якщо таких вершин немає, але залишаються вершини, що не містяться в раніше побудованих множинах S_k, вибираємо довільну з них і вважаємо, що S_2j+1 складається з цієї єдиної вершини.

• Для цілого j ≥ 1, нехай S_2j;— множина всіх вершин u, таких, що u належить деякому ребру з M з другої вершиною з S_2j−1. Зауважимо, що для будь-якої v з S_2j−1 існує вершина u, в парі, з якою вони входять в паросполучення, оскільки в іншому випадку v була б в S₀. Таким чином, M встановлює однозначну відповідність між вершинами з S_2j−1 і вершинами з S_2j.

Щодо останнього члена цього списку можуть виникнути сумніви — а чи не може статися так, що вершина u, що належить деякому ребру з M з вершиною v в S_2j-1 буде також міститися і в множинаіі S_2jз індексом, меншим 2j, звідки випливає, що множина Si не утворює окремої частини. Ми покажемо, що такого відбутися не може.

• Вершина v, що з'явилася з побудови перший раз в S_2j-1, не може разом з вершиною S_2k з k < j належати паросполученню, оскільки вершини S_2k або не містяться ні в якій дузі паросполучення (при k = 0), або утворюють дугу паросполучення разом з дугою з S_2k-1 (при k ≥ 1).

• Вершина v не може сполучатись з вершиною u ∈ S_2k-1 , k≤ j. Зауважимо, по-перше, що вершини з S_2k-1 , де k < j, сполучаються з вершинами S_2k з 2k < 2j-1 і, тому, не можуть сполучатись з v. По-друге, припустимо, що v паросполучається з u ∈ S_2j−1. Побудуємо проміжну з початком у вершині v шляхом вибору ребра з E \ M, що містить кінцеву вершину v і другу вершину зS_2j-2, ребра з M, що містить отриману вершину і вершину з S_2j-3, і так далі. Отримаємо зв'язок вершин з S_2i з вершинами з S_2i-1 ребрами з E \ M при i непарному і ребрами з M при i парному. Процес буде продовжуватися, поки або не досягнемо S₀, або множина S_2h+1 буде містити єдину вершину, що не має ребер, що з'єднують її з нижнім рівнем S_2h. Побудуємо такий же шлях, починаючи з u. Об'єднуючи ці два шляхи ребром vu з M, отримаємо більш довгий переміжний шлях P. Шлях P є простим, оскільки у разі наявності загальної вершини w на рівні i, отримали б цикл непарної довжини, що містить вершину w, що неможливо в дводольних графах. Як наслідок, кінцеві вершини шляху P повинні бути різними вершинами з S₀. Оскільки перше і останнє ребро P належать E \ M, P містить на одиницю більше ребер з E \ M ніж з M. Тоді, прибираючи ребра P ∩ M з M і додаючи ребра P ∩ (E \ M) до M ми отримаємо паросполучення з великим числом ребер, ніж в M, що суперечить максимальності M.

Ми показали, що кожна вершина множини V міститься рівно в одні множині S_2i. Звідси випливає, що ребра M завжди з'єднують вершини суміжних рівнів S_j−1 і S_2j. Покажемо, що ніяке ребро E \ M не з'єднує пару вершин, що лежать на парних рівнях. Припустимо, що ребро з E \ M з'єднує вершину з S_2j з вершиною S_2k при k ≤ j. Якщо v — вершина в S_2k k < j, то будь вершина, сполучена з v ребром з E \ M, знаходиться на рівні S_i з i ≤ 2k + 1 < 2j, а тому v не може бути пов'язана ребром з E \ M з вершиною з S_2j. З іншого боку, застосовуючи той же прийом побудови переміжного шляху, дві вершини з S_2j можуть бути пов'язані один з одним дугою з E \ M. Отже, будь ребро з M має в точності одну вершину в непарнії множині будь ребро з E \ M маємо щонайменше одну кінцеву вершину в непарному множині. Таким чином, об'єднання всіх непарних множин дасть верхове покриття з |M| вершинами.

Побудова, описана вище і використовується для доведення теореми, дає алгоритм побудови мінімального вершинного покриття за заданим максимальним паросполученням. Так, алгоритм Гопкрофта—Карпа для пошуку максимального паросполучення в дводольних графах може бути використаний для ефективного вирішення завдання про мінімальне вершинне покриття.

Всупереч еквівалентності двох завдань, з погляду точного рішення, вони абсолютно не еквівалентні для апроксимаційних алгоритмів. Завдання про максимальне паросполучення для дводольних графів може бути апроксимована з довільною точністю за постійний час за допомогою розподілених алгоритмів, на противагу завданню про мінімальне вершинне покриття, що вимагає як мінімум логарифмічного часу.[3]

Кажуть, що граф досконалий, якщо для будь-якого досконалого підграфу його хроматичне число дорівнює розміру максимальної кліки. Будь-який дводольний граф є досконалий, оскільки будь-який його підграф є або дводольним, або незалежним. У дводольному графі, що не є незалежним, хроматичне число і розмір максимальної кліки дорівнюють двом, у той час як для незалежної множини обидва числа дорівнюють одиниці.

Граф досконалий тоді і тільки тоді, коли його доповнення абсолютне (Lovász 1972), і теорему Кеніга можна вважати еквівалентом твердження, як що доповнення дводольного графу абсолютне. Будь-які розмальовки доповнення двудольного графу мають розмір максимум 2, а класи розміру 2 утворюють паросполучення. Кліки в доповненні графу G — це незалежна множина в G, і, як ми вже писали вище, незалежна множина в дводольному графі G — це доповнення верхового покриття G. Таким чином, будь-які паросполучення M в дводольному графі G з n вершинами відповідають розфарбуванні доповнення G з n- | M | кольорами, що через досконалість доповнення дводольних графів, відповідають незалежній множині в G з n- | M | вершинами, що відповідають вершинам покриттю G | M | вершинами. Отже, теорема Кеніга доводить досконалість доповнень дводольних графів, тобто результат, виражений у більш явній формі в Гала (Gallai, 1958).

Можна пов'язати також теорему Кеніга про реберне розфарбування з іншим класом досконалих графів, реберними графами дводольних графів. Для графу G реберний граф L (G) має вершини, відповідні ребрам графу G, і ребра для кожної пари суміжних ребер в G. Таким чином, хроматичне число L (G) одно хроматичного індексом G. Якщо G — двочастковий, кліки в L (G) — це в точності множина ребер в G, що мають загальну кінцеву вершину. Тепер теорема Кеніга про реберне розфарбування, яка стверджує, що хроматичний індекс дорівнює максимальному ступені вершин в дводольному графі, може бути інтерпретована як твердження, що реберний граф двудольного графу досконалий.[4]

Оскільки реберні графи дводольних графів досконалі, доповнення реберних графів дводольних графів теж досконалі. Кліка в доповненні ребрового графу для G — це просто паросполучення G. А розфарбування доповнення ребрового графу для G, у випадку, якщо G є дводольним, — це розбиття ребер графу G на підмножини ребер, що мають спільні вершини. Кінцеві вершини, які є загальними в цих підмножинах, утворюють верхове покриття графу G. Таким чином, сама теорема Кеніга може бути також інтерпретована як твердження, що доповнення реберних графів абсолютне.

• Biggs, N. L.; Lloyd, E. K.; Wilson, R. J.Теорія Графів 1736—1936. — Пресса Оксфордського Університету, 1976. — С. 203—207. — ISBN 0-19-853916-9.
• J. A. Bondy, U. S. R. Murty. Теорія графів та додатки . — North Holland, 1976. — С. 74. — ISBN 0-444-19451-7.
• Gallai, Tibor Maximum-minimum Sätze über Graphen // Acta Math. Acad. Sci. Hungar.. — 1958. — Т. 9, вип. 3-4. — С. 395—434. — DOI:10.1007/BF02020271.
• Mika Göös, Jukka Suomela.26-а Міжнародний симпозіум з розподіленим обчисленням (ДИСК), Сальвадор, Бразилія, жовтень 2012 року — 2012.
• Kőnig, Dénes Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére // Matematikai és Természettudományi Értesítő. — 1916. — Т. 34. — С. 104—119.
• Kőnig, Dénes Gráfok és mátrixok // Matematikai és Fizikai Lapok. — 1931. — Т. 38. — С. 116—119.
• László Lovász, M. D. Plummer. Відповідність теорії. — Північна Голландія, 1986. — ISBN 0-444-87916-1.
• Lovász, László Normal hypergraphs and the perfect graph conjecture // Дискретна математика. — 1972. — Т. 2, вип. 3. — С. 253—267. — DOI:10.1016/0012-365X(72)90006-4.