Это не официальный сайт wikipedia.org 01.01.2023

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

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

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

ЛитератураПравить

Источник — https://ru.wikipedia.org/w/index.php?title=Вполне_упорядочиваемый_граф&oldid=117118564