|
Досконалий граф
 Досконалим графом називається граф, у якому хроматичне число будь-якого породженого підграфу дорівнює розміру максимальної кліки цього підграфу. Відповідно до сильної теореми про досконалі графи, досконалі графи — це те саме, що й графи Берже. Граф G є графом Берже, якщо ні G, ні його додаток не мають породжених циклів, довжиною більше 5 ребер. Досконалий граф містить у собі багато досконалих сімейств графів, та забезпечують уніфікацію результатів, пов'язаних із розфарбуванням та кліками цих сімейств. Наприклад, для всіх досконалих графів задача про розфарбовування , задача про максимальну кліку та задача про максимальну незалежну множину можуть бути розв'язані за поліномінальний час. Крім того, декілька важливих мінімаксних теорем комбінаторики, такі як теорема Ділуорса, можуть бути виражені в термінах досконалих та деяких пов'язаних з ними графів. Теорія досконалих графів почала свій розвиток після роботи Тібора Галаї 1958 року, що може бути інтерпретована на сучасній мові як твердження: доповнення двочасткового графу є досконалим графом. Також це можна розглядати як простий еквівалент до теореми Кьоніга, а значно раніший результат стосується паросполучень та покриття вершин у двочасткових графах. Вперше словосполучення «досконалий граф» було вжите в 1963 році у статті Клауді Бержа, після якого було інтерпретоване як «граф Берже». У цій статті вчений пов'язав результати Галая з деякими іншими шляхом визначення досконалих графів та запропонував гіпотезу про ідентичність досконалих графів та «графів Берже», що була доведена в 2002 році як сильна теорема про досконалі графи. Родини досконалих графівДеякі з найбільш відомих сімей досконалих графів:
Зв'язок з теоремами мінімаксуУ всіх графах клікове число запроваджує нижню межу хроматичного числа, оскільки у кліці всі вершини повинні бути розфарбовані у різні кольори. Досконалі графи — ті, у яких нижня межа є точною не тільки для самого графу, а й для всіх його породжених підграфів. Для графів, що не є досконалими хроматичне та клікове число можуть не дорівнювати одне одному. Наприклад, для циклу довжиною 5 необхідно три кольори, а максимальна кількість клік — 2. Доведення, що граф є досконалим можна розглядати як теорему мінімаксу — мінімальна кількість кольорів, що потребується для розфарбування цих графів дорівнює розміру максимальної кліки. Множину важливих мінімаксних теорем комбінаторики можна виразити у наступних термінах. Наприклад, теорема Ділоурса стверджує, що мінімальне число ланцюгів при діленні частково впорядкованої множини на ланцюги дорівнює максимальному розміру антиланцюгів, та може бути перефразована як ствердження, що доповнення графів порівнянності є досконалими. Теорема Мірського стверджує, що мінімальна кількість антиланцюгів при діленні на антиланцюги рівна максимальному розміру ланцюгів та відповідає таким самим чином досконалості графів порівнянності. Досконалість графів перестановки еквівалентна твердженню, що в будь-якій послідовності впорядкованих елементів довжина найдовшої спадної послідовності дорівнює мінімальному числу послідовностей при поділі на зростаючі послідовності. Теорема Ердьоша-Секереша легко виводиться саме з цього твердження. Теорема Кьоніга в теорії графів стверджує, що мінімальне покриття вершин двочасткового графу відповідає максимальному паруванню і навпаки. Її можна інтерпретувати як досконалість доповнень двочасткових графів. Інша теорема про двочасткові графи, про те, що двочастковий індекс дорівнює максимальному степеню графу еквівалентна досконалості реберного графу двочасткових графів. Характеристики та теореми при досконалі графиУ своїй першій роботі про досконалі графи Берж висловив дві важливі гіпотези про їх будову, котрі були доведені пізніше. Першої з цих теорем була теорема про досконалі графи Ласло Ловаса (1972), у якій йшлося про те, що граф є досконалим тоді і тільки тоді, коли його доповнення є досконалим. Таким чином, досконалість (визначена як рівність розміру максимальної кліки та хроматичного числа у кожному породженому підграфі) еквівалентне максимуму розміру незалежної множини та числу клікового покриття.  Друга теорема, висловлена Бержем як гіпотеза, забезпечувала характеризацію забороненими графами для досконалого графу. Породжений цикл непарної довжини більшої за 5 має назву дірки непарної довжини. Породжений підграф, що є доповненням до непарної дірки, називається непарною антидіркою. Непарний цикл довжиною більше за 3 не може бути досконалим, тому що його хроматичне число 3, а число клік 2. Також доповнений граф непарного циклу довжини 2k + 1 не може бути досконалим, тому що його хроматичним числом є k + 1, а число кліки k. (Зверніть увагу на те, що недосконалість цього графу виходить з теореми про досконалість графу та недосконалість доповнень непарних циклів). Оскільки ці графи недосконалі, кожний досконалий граф має бути графом Бержа, графом без непарних дірок та без непарних антидірок. Берж стверджував, що будь-який граф Бержа є досконалим. Це остаточно доведено сильною теоремою про досконалі графи Чудновської, Робертсона, Сеймора та Томаса (2006). Теорема про досконалий граф має коротке доведення, проте доведення сильної теореми про досконалі графи довге та складне, спирається та структурну декомпозицію графів Бержа. Близькі методи декомпозиції народилися також у результаті вивчення інших класів графів, наприклад, графів без клешень. Алгоритми на досконалих графахДля усіх досконалих графів задача про розфарбування, задача про максимальну кліку та задача про максимальну незалежну множину можуть бути вирішені в поліноміальний час (Грьочел, Ловас та Шрійвер 1988). Алгоритм для загальних випадків використовує метод еліпсоїдів, лінійного програмування, але найбільш ефективними є комбінаторні алгоритми, відомі для багатьох конкретних випадків. Впродовж багатьох років питання про обчислення складності розпізнання графів Бержа та досконалих графів залишалось відкритим. Із визначення графів Бержа слідує, що їх розпізнання є задачею з сo-NP. Отже, після доведення сильної теореми про досконалі графи, Чудновською, Корнейолсом, Луї, Сеймором та Вуйковічем був сформований поліноміальний алгоритм. Див. також
Література
|
