Идеально упорядочиваемый граф
Частный случай идеальных графов в теории графов

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

Определение

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

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

Сложность вычислений

Идеально упорядочиваемые графы являются NP-полными для распознавания. [2] Однако легко проверить, является ли конкретный порядок идеальным порядком графа. Следовательно, также NP-трудно найти идеальный порядок графа, даже если уже известно, что граф идеально упорядочиваем.

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

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

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

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

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

Известно несколько дополнительных классов совершенно упорядочиваемых графов. [7]

Примечания

  1. ^ abc Chvátal (1984); Маффрэ (2003).
  2. ^ Миддендорф и Пфайффер (1990); Маффрэ (2003).
  3. ^ Голумбик, Монма и Троттер (1984).
  4. ^ Паян (1983); Фельснер, Рагхаван и Спинрад (2003).
  5. ^ Хоанг и Рид (1989); Брандштедт, Ле и Спинрад (1999), стр. 70 и 82.
  6. ^ Брандштедт, Ле и Спинрад (1999), теорема 5.2.4, с. 71.
  7. ^ Хватал и др. (1987); Хоанг и Рид (1989); Хоанг и др. (1992); Маффрэ (2003); Брандштедт, Le & Spinrad (1999), стр. 81–86.

Ссылки

  • Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: Обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X
  • Кристен, Клод А.; Селков, Стэнли М. (1979), «Некоторые свойства идеальной раскраски графов», Журнал комбинаторной теории , Серия B, 27 (1): 49–59, doi :10.1016/0095-8956(79)90067-4, MR  0539075
  • Chvátal, Václav (1984), «Совершенно упорядочиваемые графы», в Berge, Claude ; Chvátal, Václav (ред.), Topics in Perfect Graphs , Annals of Discrete Mathematics, т. 21, Амстердам: North-Holland, стр. 63–68. Как цитирует Маффрей (2003).
  • Chvátal, Václav ; Hoàng, Chính T.; Mahadev, NVR; De Werra, D. (1987), "Четыре класса совершенно упорядочиваемых графов", Journal of Graph Theory , 11 (4): 481–495, doi :10.1002/jgt.3190110405.
  • Драган, ФФ; Николай, Ф. (1995), LexBFS-упорядочение дистанционно-наследственных графов , Schriftenreihe des Fachbereichs Mathematik der Univ. Дуйсбург SM-DU-303. Как цитируется по Brandstädt, Le & Spinrad (1999).
  • Фелснер, Стефан; Рагхаван, Виджай; Спинрад, Джереми (2003), «Алгоритмы распознавания для порядков малой ширины и графиков малого числа Дилворта», Order , 20 (4): 351–364 (2004), doi :10.1023/B:ORDE.0000034609.99940.fb, MR  2079151, S2CID  1363140.
  • Golumbic, Martin Charles ; Monma, Clyde L.; Trotter, William T. Jr. (1984), «Графики толерантности», Discrete Applied Mathematics , 9 (2): 157–170, doi : 10.1016/0166-218X(84)90016-7 , MR  0761599
  • Хоанг, Чин Т.; Маффрей, Фредерик; Олариу, Стефан; Прейсманн, Мириам (1992), «Очаровательный класс совершенно упорядочиваемых графов», Дискретная математика , 102 (1): 67–74, doi : 10.1016/0012-365X(92)90348-J.
  • Хоанг, Чин Т.; Рид, Брюс А. (1989), «Некоторые классы совершенно упорядочиваемых графов», Журнал теории графов , 13 (4): 445–463, doi :10.1002/jgt.3190130407.
  • Maffray, Frédéric (2003), «О раскраске совершенных графов», в Reed, Bruce A. ; Sales, Cláudia L. (ред.), Recent Advances in Algorithms and Combinatorics , CMS Books in Mathematics, т. 11, Springer-Verlag, стр. 65–84, doi :10.1007/0-387-22444-0_3, ISBN 0-387-95434-1.
  • Миддендорф, Маттиас; Пфайффер, Франк (1990), «О сложности распознавания совершенно упорядочиваемых графов», Дискретная математика , 80 (3): 327–333, doi : 10.1016/0012-365X(90)90251-C.
  • Пайан, Чарльз (1983), «Совершенство и число Дилворта», Дискретная математика , 44 (2): 229–230, doi : 10.1016/0012-365X(83)90064-X , MR  0689816.
Взято с "https://en.wikipedia.org/w/index.php?title=Идеально_упорядочиваемый_график&oldid=1234815183"