Теорема про досконалі графи

Теоре́ма про доскона́лі гра́фи Ловаса — твердження про те, що неорієнтований граф є досконалим тоді й лише тоді, коли його доповнення також досконале. Це твердження, яке висловив у вигляді гіпотези ^[en], називають іноді слабкою теоремою про досконалі графи, щоб не змішувати зі сильною теоремою про досконалі графи, яка описує досконалі графи їхніми забороненими породженими підграфами.

Твердження теореми

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

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

Теорема про досконалі графи стверджує:

Доповнення досконалого графа досконале.

Еквівалентне формулювання: в досконалому графі розмір найбільшої незалежної множини дорівнює найменшому числу клік у кліковому покритті.

Приклад

Цикл зі сімома вершинами та його доповнення, антидіра зі сімома вершинами. На малюнку показано оптимальні розфарбування та найбільші кліки (показані жирними ребрами). Оскільки в обох графах кількість кольорів не збігається з розміром кліки, обидва графи не є досконалими.

Нехай G — граф-цикл непарної довжини, більшої за три (так звана «непарна діра»). Тоді для будь-якого розфарбування G потрібно щонайменше три кольори, але немає жодного трикутника, так що граф не досконалий. Тому, за теоремою про досконалі графи, доповнення графа G («непарна антидіра») має також бути недосконалим. Якщо граф G є циклом із п'яти вершин, він ізоморфний своєму доповненню, але це неправильно для довших циклів. Нетривіальною задачею є обчислення клікового числа та хроматичного числа в непарній антидірі та непарній дірі. Як стверджує сильна теорема про досконалі графи, непарні діри і непарні антидіри виявляються найменшими забороненими породженими підграфами досконалих графів.

Застосування

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

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

Доведення Ловаса

Для доведення теореми про досконалі графи Ловас використовував операцію заміни вершин у графі кліками. Вже Бержу було відомо, що якщо граф досконалий, отриманий такою заміною граф також буде досконалим. Будь-який такий процес заміни можна розбити на повторювані кроки дублювання вершин. Якщо вершина, що дублюється, належить найбільшій кліці графа, вона збільшує клікове число і хроматичне число на одиницю. Якщо, з іншого боку, вершина, що дублюється, не належить найбільшій кліці, утворюємо граф H видаленням вершин того ж кольору, що й дубльована (але не саму дубльовану вершину) з оптимального розфарбування графа. Вершини, що видаляються, входять у всі найбільші кліки, так що H має число клік і хроматичне число на одиницю менше, ніж у початковому графі. Видалені вершини та нові копії задубльованих вершин можна додати до єдиного класу кольору, що показує, що крок дублювання не змінює хроматичного числа. Ті ж міркування показують, що подвоєння зберігає рівність числа клік хроматичному числу в кожному породженому підграфі даного графа, так що кожен крок подвоєння зберігає досконалість графа.

Якщо задано досконалий граф G, Ловас утворює граф G*, замінюючи кожну вершину v клікою з t_v вершинами, де t_v — число різних максимальних множин у G, що містять v. Можна зіставити кожній із різних максимальних незалежних множин із G максимальну незалежну множину G* так, що незалежні множини в G* всі не будуть перетинатися і кожна вершина G* з'явиться в єдиній вибраній множині. Тобто G* має розфарбування, в якому кожен клас кольору є максимальною незалежною множиною. Це розфарбування обов'язково буде оптимальним розфарбуванням G*. Оскільки G досконалий, таким є і G*, а тоді він має максимальну кліку K*, розмір якої дорівнює числу кольорів у цьому розфарбуванні, що дорівнює числу різних максимальних незалежних множин G. Обов'язково K* містить різні подання для кожної з цих максимальних множин. Відповідна множина K вершин у G (вершин, розширені кліки яких у G* перетинають K*) є клікою G зі властивістю, що вона перетинає будь-яку максимальну незалежну множину G. Таким чином, граф, утворений з G видаленням K має число клікового покриття, що не перевищує клікового числа графа G без одиниці, а число незалежності щонайменше на одиницю менше від числа незалежності графа G. Результат випливає з індукції за цим числом.

Стосунок до сильної теореми про досконалі графи

Сильна теорема про досконалі графи Чудновської, Робертсона, Сеймура і Томаса стверджує, що граф є досконалим тоді й лише тоді, коли жоден із породжених підграфів не є циклом непарної довжини, більшої або рівної п'яти, а також не є доповненням такого циклу. Оскільки такий опис нечутливий до операції доповнення графа, звідси негайно випливає слабка теорема про досконалі графи.

Узагальнення

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

Примітки

1. Lovász, 1972a.
2. Lovász, 1972b.
3. Berge, 1961.
4. Berge, 1963.
5. Її сформулював як гіпотезу також Берж, але довели її значно пізніше Чудновська, Робертсон, Сеймур і Томас (Chudnovsky, Robertson, Seymour, Thomas, 2006).
6. Kőnig, 1931; Пізніше теорему перевідкрив Галаї Gallai, 1958.
7. Golumbic, 1980, с. 132–135, Section 5.7, "Coloring and other problems on comparability graphs".
8. Див. книгу Колумбіка (Golumbic, 1980), Lemma 3.1(i), і Ріда (Reed, 2001), Corollary 2.21.
9. Reed, 2001, с. Lemma 2.20.
10. Ми виклали доведення за Рідом (Reed, 2001). Колумбік (Golumbic, 1980) зауважив, що більшість із наведених міркувань швидко отримав Фулкерсон, коли прослухав доповідь Ловаса, але навіть не бачив його доведення.
11. Chudnovsky, Robertson, Seymour, Thomas, 2006.
12. Cameron, Edmonds, Lovász, 1986.

Література

• Claude Berge. Färbung von Graphen, deren sämtliche beziehungsweise deren ungerade Kreise starr sind // Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-naturwissenschaftliche Reihe. — 1961. — Bd. 10. — S. 114.
• Claude Berge. Perfect graphs // Six Papers on Graph Theory. — Calcutta : Indian Statistical Institute, 1963. — С. 1–21.
• K. Cameron, J. Edmonds, L. Lovász. A note on perfect graphs // Periodica Mathematica Hungarica. — 1986. — Т. 17, вип. 3. — С. 173–175. — DOI:10.1007/BF01848646.
• Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вип. 1. — С. 51–229. — DOI:10.4007/annals.2006.164.51.
• Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Progress on perfect graphs // . — 2003. — Т. 97, вип. 1-2. — С. 405–422. — (Series B.). — DOI:10.1007/s10107-003-0449-8.
• Tibor Gallai. Maximum-minimum Sätze über Graphen // Acta Mathematica Academiae Scientiarum Hungarica. — 1958. — Bd. 9, H. 3-4. — S. 395–434. — DOI:10.1007/BF02020271.
• Martin Charles Golumbic. 3.2. The perfect graph theorem // Algorithmic Graph Theory and Perfect Graphs. — New York : Academic Press, 1980. — С. 53–58. — .
• Dénes Kőnig. Gráfok és mátrixok // Matematikai és Fizikai Lapok. — 1931. — Köt. 38. — O. 116–119.
• László Lovász. Normal hypergraphs and the perfect graph conjecture // . — 1972a. — Т. 2, вип. 3. — С. 253–267. — DOI:10.1016/0012-365X(72)90006-4.
• László Lovász. A characterization of perfect graphs // . — 1972b. — Т. 13, вип. 2. — С. 95–98. — (Series B). — DOI:10.1016/0095-8956(72)90045-7.
• Bruce Reed. From conjecture to theorem // Perfect Graphs / Jorge L. Ramírez Alfonsín, Bruce A. Reed. — Chichester : Wiley, 2001. — С. 13–24. — (Wiley-Interscience Series on Discrete Mathematics and Optimization)