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

Ця стаття є сирим перекладом з іншої мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. Будь ласка, допоможіть поліпшити переклад. (березень 2016)

Цю статтю треба вікіфікувати для відповідності стандартам якості Вікіпедії. Будь ласка, допоможіть додаванням доречних внутрішніх посилань або вдосконаленням розмітки статті. (квітень 2020)

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

Теорема названа на честь угорського математика Денеша Кеніга. Кеніг заявив про неї в 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.