Цілком упорядковуваний граф

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

Визначення

Алгоритм жадібного розфарбовування, коли він застосовується до заданого упорядкування вершин графу G, розглядає послідовно вершини графу (згідно з порядком) і призначає кожній вершині перший доступний колір. Різні упорядкування вершин можуть приводити до різного числа необхідних кольорів. Завжди існує впорядкування, яке веде до оптимального розфарбування — це істинне, наприклад, при упорядкуванні вершин за кольорами оптимального розфарбування, але таке впорядкування, іноді, складно знайти. Цілком упорядковувані графи, за визначенням, це графи, для яких існує впорядкування, оптимальне для алгоритму жадібного розфарбовування не тільки для самого графу, але й для всіх його породжених підграфів.

Формальніше, кажуть, що граф G цілком упорядковуваний, якщо існує впорядкування π вершин графу G, таке, що будь-який породжений підграф графу G оптимально розфарбовується алгоритмом жадібного розфарбовування за використання підпослідовності упорядкування π, породженої вершинами підграфу. Впорядкування π має цю властивість точно тоді, коли не існує чотирьох вершин a, b, c і d, для яких abcd є породженим підграфом, у якому a стоїть перед b (в упорядкуванні), а c стоїть після d.

Обчислювальна складність

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

Пов'язані класи графів

Будь-який цілком упорядковуваний граф є досконалим.

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

Ще один клас цілком упорядковуваних графів складається з графів G, таких, що в будь-якій підмножині з п'яти вершин з графу G щонайменше одна з п'яти вершин має замкнутий окіл, який є підмножиною (або дорівнює) замкнутим околам інших вершин з п'ятірки. Еквівалентно, це графи, в яких частковий порядок замкнутих околів, який визначається включенням множин, має ширину, яка не перевищує 4. Граф-цикл із 5 вершинами має ширину часткового порядку околів, рівну п'яти, так що число чотири є максимальною шириною, що забезпечує досконале впорядкування. Як і в разі хордальних графів (але, в загальному випадку, не для цілком упорядковуваних графів узагалі) графи з шириною чотири розпізнаються за поліноміальний час.

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

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

Відомі деякі інші класи цілком упорядковуваних графів.

Примітки

1. Chvátal, 1984.
2. Maffray, 2003.
3. Middendorf, Pfeiffer, 1990.
4. Payan, 1983.
5. Felsner, Raghavan, Spinrad, 2003.
6. Hoàng, Reed, 1989.
7. Brandstädt, Le, Spinrad, 1999, с. 70, 82.
8. Brandstädt, Le, Spinrad, 1999, с. 71, Theorem 5.2.4.
9. Christen, Selkow, 1979.
10. Chvátal, Hoàng, Mahadev, De Werra, 1987.
11. Hoàng, Maffray, Olariu, Preissmann, 1992.
12. Brandstädt, Le, Spinrad, 1999, с. 81–86.

Література

• Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — .
• Claude A. Christen, Stanley M. Selkow. Some perfect coloring properties of graphs // . — 1979. — Т. 27, вип. 1. — С. 49–59. — (Series B). — DOI:10.1016/0095-8956(79)90067-4.
• Václav Chvátal. Topics in Perfect Graphs / Claude Berge, Václav Chvátal. — Amsterdam : North-Holland, 1984. — Т. 21. — С. 63–68. — (Annals of Discrete Mathematics). Як процитовано в Маффрея (Maffray, (2003)).
• Václav Chvátal, Chính T. Hoàng, N. V. R. Mahadev, D. De Werra. Four classes of perfectly orderable graphs // Journal of Graph Theory. — 1987. — Т. 11, вип. 4. — С. 481–495. — DOI:10.1002/jgt.3190110405..
• F. F. Dragan, F. Nicolai. LexBFS-orderings of distance-hereditary graphs. — (Schriftenreihe des Fachbereichs Mathematik der Univ. Duisburg SM-DU-303). Як процитовано в Бранштедта (Brandstädt, Le та Spinrad, (1999)).
• Stefan Felsner, Vijay Raghavan, Jeremy Spinrad. Recognition algorithms for orders of small width and graphs of small Dilworth number // . — 2003. — Т. 20, вип. 4. — С. 351–364 (2004). — DOI:10.1023/B:ORDE.0000034609.99940.fb..
• Chính T. Hoàng, Frédéric Maffray, Stephan Olariu, Myriam Preissmann. A charming class of perfectly orderable graphs // . — 1992. — Т. 102, вип. 1. — С. 67–74. — DOI:10.1016/0012-365X(92)90348-J..
• Chính T. Hoàng, Bruce A. Reed. Some classes of perfectly orderable graphs // Journal of Graph Theory. — 1989. — Т. 13, вип. 4. — С. 445–463. — DOI:10.1002/jgt.3190130407..
• Frédéric Maffray. Recent Advances in Algorithms and Combinatorics / Bruce A. Reed, Cláudia L. Sales. — Springer-Verlag, 2003. — Т. 11. — С. 65–84. — (CMS Books in Mathematics) — . — DOI:10.1007/0-387-22444-0_3..
• Matthias Middendorf, Frank Pfeiffer. On the complexity of recognizing perfectly orderable graphs // . — 1990. — Т. 80, вип. 3. — С. 327–333. — DOI:10.1016/0012-365X(90)90251-C..
• Charles Payan. Perfectness and Dilworth number // . — 1983. — Т. 44, вип. 2. — С. 229–230. — DOI:10.1016/0012-365X(83)90064-X..