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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Література[ред. | ред. код]