Досконалий граф

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

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

Досконалий граф містить у собі багато досконалих сімейств графів, та забезпечують уніфікацію результатів, пов'язаних із розфарбуванням та кліками цих сімейств. Наприклад, для всіх досконалих графів задача про розфарбовування , задача про максимальну кліку та задача про максимальну незалежну множину можуть бути розв'язані за поліномінальний час. Крім того, декілька важливих мінімаксних теорем комбінаторики, такі як теорема Ділуорса, можуть бути виражені в термінах досконалих та деяких пов'язаних з ними графів.

Теорія досконалих графів почала свій розвиток після роботи Тібора Галаї 1958 року, що може бути інтерпретована на сучасній мові як твердження: доповнення двочасткового графу є досконалим графом. Також це можна розглядати як простий еквівалент до теореми Кьоніга, а значно раніший результат стосується паросполучень та покриття вершин у двочасткових графах. Вперше словосполучення «досконалий граф» було вжите в 1963 році у статті Клауді Бержа, після якого було інтерпретоване як «граф Берже». У цій статті вчений пов'язав результати Галая з деякими іншими шляхом визначення досконалих графів та запропонував гіпотезу про ідентичність досконалих графів та «графів Берже», що була доведена в 2002 році як сильна теорема про досконалі графи.

Родини досконалих графів ред.

Деякі з найбільш відомих сімей досконалих графів:

Двочасткові графи — графи, що можуть бути пофарбованими у два кольори, у тому числі й графи без циклів.
Реберні графи двочасткових графів (див. теорему Кьоніга). Особливим випадком є ладейні графи (реберні графи повних двочасткових графів).
Хордові графи — графи, в яких кожен цикл з чотирьох або більше вершин має хорду (ребро між двома вершинами, які не з'єднуються послідовно у циклі). Ця родина містить ліси, k-дерева (максимальні графи з заданою шириною дерева), відокремлені графи (графи, що можна розбити на кліки та незалежні множини), блокові графи (у яких будь-яка компонента двозв'язності є клікою), інтервальні графи (графи, у яких кожна вершина відповідає відрізку на прямій, а кожне ребро — непустий перетин відрізків), тривіально досконалі графи (інтервальні графи для вкладених інтервалів), порогові графи (графи, у яких дві вершини суміжні, коли їх спільна вага більше за визначений поріг), вітряки (утворені об'єднанням однакових клік та мають одну спільну для усіх клік точку), сильні хордові графи (хордові графи, у яких кожен цикл рівний або більше шести має непарну хорду).
Граф порівнянності, утворений з частково впорядкованих множин шляхом поєднання пар елементів ребром, якщо вони пов'язані частковим порядком. Ця родина містить двочасткові графи, доповнення інтервальних графів, тривіально досконалі графи, порогові графи, вітряки, графи перестановки (графи, у яких ребра відповідають парам елементів, що йдуть у оберненому порядку) та кографи (графи, утворені рекурсивними операціями об'єднання доповнень з графами, що не перетинаються).
Цілком упорядковані графи — графи, які можна впорядкувати таким чином, що алгоритм жадібного забарвлення стає оптимальним для будь-якого породженого підграфу. Ця родина містить двочасткові графи, хордові графи, графи порівнянності, дистанційно-наслідувальні графи (у яких найкоротша відстань у зв'язних породжених підграфах дорівнює найкоротшій відстані у самому графі) та вітряки, що мають непарну кількість вершин.
Трапецієдальні графи — графи перетину трапецій, у яких основи лежать на двох паралельних прямих. Ця родина містить інтервальні графи, тривіально досконалі графи, порогові графи, вітряки та графи перестановок. Множина доповнень до цих графів є підмножиною графів порівнянності.

Зв'язок з теоремами мінімаксу ред.

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

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

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

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

Характеристики та теореми при досконалі графи ред.

У своїй першій роботі про досконалі графи Берж висловив дві важливі гіпотези про їх будову, котрі були доведені пізніше.

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

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

Друга теорема, висловлена Бержем як гіпотеза, забезпечувала характеризацію забороненими графами для досконалого графу. Породжений цикл непарної довжини більшої за 5 має назву дірки непарної довжини. Породжений підграф, що є доповненням до непарної дірки, називається непарною антидіркою. Непарний цикл довжиною більше за 3 не може бути досконалим, тому що його хроматичне число 3, а число клік 2. Також доповнений граф непарного циклу довжини 2k + 1 не може бути досконалим, тому що його хроматичним числом є k + 1, а число кліки k. (Зверніть увагу на те, що недосконалість цього графу виходить з теореми про досконалість графу та недосконалість доповнень непарних циклів). Оскільки ці графи недосконалі, кожний досконалий граф має бути графом Бержа, графом без непарних дірок та без непарних антидірок. Берж стверджував, що будь-який граф Бержа є досконалим. Це остаточно доведено сильною теоремою про досконалі графи Чудновської, Робертсона, Сеймора та Томаса (2006).

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

Алгоритми на досконалих графах ред.

Для усіх досконалих графів задача про розфарбування, задача про максимальну кліку та задача про максимальну незалежну множину можуть бути вирішені в поліноміальний час (Грьочел, Ловас та Шрійвер 1988). Алгоритм для загальних випадків використовує метод еліпсоїдів, лінійного програмування, але найбільш ефективними є комбінаторні алгоритми, відомі для багатьох конкретних випадків.

Впродовж багатьох років питання про обчислення складності розпізнання графів Бержа та досконалих графів залишалось відкритим. Із визначення графів Бержа слідує, що їх розпізнання є задачею з сo-NP. Отже, після доведення сильної теореми про досконалі графи, Чудновською, Корнейолсом, Луї, Сеймором та Вуйковічем був сформований поліноміальний алгоритм.

Див. також ред.

Література ред.

Berge, Claude (1961). Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. Т. 10. с. 114.
Berge, Claude (1963). Perfect graphs. Six Papers on Graph Theory. Calcutta: Indian Statistical Institute. с. 1—21.
Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). Recognizing Berge graphs. Combinatorica. Т. 25, № 2. с. 143—186. doi:10.1007/s00493-005-0012-8. CS1 maint: Multiple names: authors list (link)
Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). The strong perfect graph theorem. Annals of Mathematics. Т. 164, № 1. с. 51—229. doi:10.4007/annals.2006.164.51. Архів оригіналу за 18 червня 2010. Процитовано 28 травня 2016.
Gallai, Tibor (1958). Maximum-minimum Sätze über Graphen. Acta Math. Acad. Sci. Hungar. Т. 9, № 3-4. с. 395—434. doi:10.1007/BF02020271.
Golumbic, Martin Charles (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press. ISBN 0-444-51530-5. Архів оригіналу за 22 травня 2010. Процитовано 28 травня 2016. Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988). Geometric Algorithms and Combinatorial Optimization. Springer-Verlag.. See especially chapter 9, «Stable Sets in Graphs», pp. 273–303.
Lovász, László (1972). Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics. Т. 2, № 3. с. 253—267. doi:10.1016/0012-365X(72)90006-4.
Lovász, László (1972). A characterization of perfect graphs. Journal of Combinatorial Theory, Series B. Т. 13, № 2. с. 95—98. doi:10.1016/0095-8956(72)90045-7.
Lovász, László (1983). Perfect graphs. У Beineke, Lowell W.; Wilson, Robin J. (Eds.) (ред.). Selected Topics in Graph Theory, Vol. 2. Academic Press. с. 55—87. ISBN 0-12-086202-6. CS1 maint: Multiple names: editors list (link)