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

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

Приклад дводольного графу з найбільшим парування (виділено блакитним) і мінімальним вершинним покриттям (виділено червоним), обидва мають розмір шість.

Історія

Теорема названа на честь угорського математика Денеша Кеніга. Кеніг заявив про неї в 1914 і опублікував в 1916 доказ, що будь-який регулярний дводольний граф має зроблене парування, і, узагальнено, що хроматичний індекс будь-якого двудольного графу (тобто мінімальне число паросполучень, на які можна розкласти всі дуги графу) дорівнює максимальному ступені. Останнє твердження відоме як теорема Кеніга про реберне розфарбування. Однак Бонді і Мерфі (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| вершинами.

Алгоритм

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

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

Зв'язок з досконалими графами

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

Граф досконалий тоді і тільки тоді, коли його доповнення абсолютне (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, що мають загальну кінцеву вершину. Тепер теорема Кеніга про реберне розфарбування, яка стверджує, що хроматичний індекс дорівнює максимальному ступені вершин в дводольному графі, може бути інтерпретована як твердження, що реберний граф двудольного графу досконалий.

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

Примітки

1. Biggs, 1976.
2. Lovász, 1986, с. 37, Theorem 1.4.17.
3. Göös, 2012.
4. Lovász, (1974).

Посилання

• 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.