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

У теорії графів теорема Кеніга, доведена Денешем Кенігом в 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. Таким чином, сама теорема Кеніга може бути також інтерпретована як твердження, що доповнення до реберних графів абсолютне.