Вполне упорядочиваемый граф

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение[править | править код]

Алгоритм жадной раскраски, когда он применяется к заданному упорядочению вершин графа G, рассматривает последовательно вершины графа (согласно порядку) и назначает каждой вершине первый доступный цвет. Различные упорядочения вершин могут приводить к разному числу потребовавшихся цветов. Всегда существует упорядочение, которое ведёт к оптимальной раскраске – это верно, например, при упорядочении вершин согласно цветам оптимальной раскраски, но такое упорядочение, может случиться, трудно найти. Вполне упорядочиваемые графы, по определению, это графы, для которых существует упорядочение, оптимальное для алгоритма жадной раскраски не только для самого графа, но и для всех его порождённых подграфов.

Более формально, говорят, что граф G вполне упорядочиваемый, если существует упорядочение π вершин графа G, такое, что любой порождённый подграф графа G оптимально раскрашивается алгоритмом жадной раскраски при использовании подпоследовательности упорядочения π, порождённой вершинами подграфа. Упорядочение π имеет это свойство в точности тогда, когда не существует четырёх вершин a, b, c и d, для которых abcd является порождённым подграфом, в котором a стоит перед b (в упорядочении), а c стоит после d[1][2].

Вычислительная сложность[править | править код]

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

Связанные классы графов[править | править код]

Любой вполне упорядочиваемый граф является совершенным.[1][2]

Хордальные графы являются вполне упорядочиваемыемыми. Совершенный порядок хордальных графов можно найти путём обращения упорядочения совершенного исключения для графа. Таким образом, применение алгоритма жадной раскраски к совершенному упорядочению обеспечивает эффективный алгоритм раскраски хордальных графов. Графы сравнимости также являются вполне упорядочиваемыемыми, где совершенное упорядочение определяется топологическим порядком транзитивной ориентации графа[1][2].

Ещё один класс вполне упорядочиваемыемых графов состоит из графов G, таких, что в любом подмножестве из пяти вершин из графа G по меньшей мере одна из пяти вершин имеет замкнутую окрестность, которая является подмножеством (или равна) замкнутым окрестностям других вершин из пятёрки. Эквивалентно, это графы, в которых частичный порядок замкнутых окрестностей, определяемый включением множеств, имеет ширину, не превосходящую 4. Граф-цикл с 5 вершинами имеет ширину частичного порядка окрестностей, равную пяти, так что число четыре является максимальной шириной, обеспечивающей совершенное упорядочение. Как и в случае хордальных графов (но, в общем случае, не для вполне упорядочиваемыемых графов вообще) графы с шириной четыре распознаются за полиномиальное время[4][5].

Концепция между порядком совершенного исключения для хордальных графов и совершенным упорядочением — понятие порядка полусовершенного исключения. В концепции совершенного исключения нет порождённого пути из трёх вершин, в котором средняя вершина исключается первой, а в порядке полусовершенного исключения нет порождённых путей из четырёх вершин, в котором одна из средних вершин удаляется раньше других из четвёрки. Обращение такого упорядочения, таким образом, удовлетворяет требованиям совершенного упорядочения, так что графы с порядком полусовершенного исключения являются вполне упорядочиваемыми[6][7]. В частности, алгоритм лексикографического поиска в ширину, используемый для поиска порядка совершенного исключения для хордальных графов, может быть использован для поиска порядка полусовершенного исключения дистанционно-наследуемых графов, которые, таким образом, также являются вполне упорядочиваемыми[8].

Графы, для которых любое упорядочение вершин является совершенным — это кографы, одновременно и хордальные, и дистанционно-наследуемые графы[9]. Поскольку кографы не содержат порождённые пути из четырёх вершин, они не могут нарушить требования упорядочения путей в совершенном порядке.

Известны некоторые другие классы вполне упорядочиваемыемых графов[10][6][11][2][12].

Примечания[править | править код]

  1. ↑ 1 2 3 Chvátal, 1984.
  2. ↑ 1 2 3 4 5 Maffray, 2003.
  3. ↑ Middendorf, Pfeiffer, 1990.
  4. ↑ Payan, 1983.
  5. ↑ Felsner, Raghavan, Spinrad, 2003.
  6. ↑ 1 2 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. — ISBN 0-89871-432-X.
  • Claude A. Christen, Stanley M. Selkow. Some perfect coloring properties of graphs // Journal of Combinatorial Theory. — 1979. — Т. 27, вып. 1. — С. 49–59. — 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 // Order. — 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 // Discrete Mathematics. — 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). — ISBN 0-387-95434-1. — doi:10.1007/0-387-22444-0_3..
  • Matthias Middendorf, Frank Pfeiffer. On the complexity of recognizing perfectly orderable graphs // Discrete Mathematics. — 1990. — Т. 80, вып. 3. — С. 327–333. — doi:10.1016/0012-365X(90)90251-C..
  • Charles Payan. Perfectness and Dilworth number // Discrete Mathematics. — 1983. — Т. 44, вып. 2. — С. 229–230. — doi:10.1016/0012-365X(83)90064-X..
Источник — https://ru.wikipedia.org/w/index.php?title=Вполне_упорядочиваемый_граф&oldid=117118564