Идеально упорядоченный график

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

Определение

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

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

Вычислительная сложность

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

Связанные классы графов

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

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

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

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

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

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

Ссылки

• Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN  0-89871-432-Х
• Кристен, Клод А.; Селков, Стэнли М. (1979), «Некоторые идеальные свойства раскраски графов», Журнал комбинаторной теории , серия B, 27 (1): 49–59, doi : 10.1016/0095-8956(79)90067-4 , MR   0539075
• Хватал, Вацлав (1984), «Идеально упорядочиваемые графы», Берже, Клод ; Хватал, Вацлав (ред.), Темы в совершенных графах , Анналы дискретной математики, том. 21, Амстердам: Северная Голландия, стр. 63–68 . Цитируется Маффреем (2003) .
• Хватал, Вацлав ; Хоанг, Чинь Т.; Махадев, NVR; Де Верра, Д. (1987), «Четыре класса идеально упорядочиваемых графов», Journal of Graph Theory , 11 (4): 481–495, doi : 10.1002/jgt.3190110405 .
• Драган, ФФ; Николай, Ф. (1995), LexBFS-упорядочения дистанционно-наследственных графов , серия публикаций кафедры математики Univ. Дуйсбург SM-DU-303 . Цитируется Брандштедтом, Ле и Спинрадом (1999) .
• Фельснер, Стефан; Рагхаван, Виджай; Спинрад, Джереми (2003), «Алгоритмы распознавания порядков малой ширины и графов малого числа Дилворта» , Order , 20 (4): 351–364 (2004), doi : 10.1023/B:ORDE.0000034609.99940.fb , MR   2079151 , S2CID   1363140 .
• Голумбик, Мартин Чарльз ; Монма, Клайд Л.; Троттер, Уильям Т. младший (1984), «Графики допусков», Discrete Applied Mathematics , 9 (2): 157–170, doi : 10.1016/0166-218X(84)90016-7 , MR   0761599
• Хоанг, Чинь Т.; Маффрэ, Фредерик; Олариу, Стефан; Прейссманн, Мириам (1992), «Очаровательный класс идеально упорядочиваемых графов» , Discrete Mathematics , 102 (1): 67–74, doi : 10.1016/0012-365X(92)90348-J .
• Хоанг, Чинь Т.; Рид, Брюс А. (1989), «Некоторые классы совершенно упорядочиваемых графов», Journal of Graph Theory , 13 (4): 445–463, doi : 10.1002/jgt.3190130407 .
• Маффрэ, Фредерик (2003), «О раскраске идеальных графов», Рид, Брюс А .; Продажи, Клаудия Л. (ред.), «Последние достижения в области алгоритмов и комбинаторики» , Книги CMS по математике, том. 11, Springer-Verlag, стр. 65–84, номер документа : 10.1007/0-387-22444-0_3 , ISBN.  0-387-95434-1 .
• Миддендорф, Матиас; Пфайффер, Франк (1990), «О сложности распознавания идеально упорядочиваемых графов», Discrete Mathematics , 80 (3): 327–333, doi : 10.1016/0012-365X(90)90251-C .
• Паян, Чарльз (1983), «Совершенство и число Дилворта», Discrete Mathematics , 44 (2): 229–230, doi : 10.1016/0012-365X(83)90064-X , MR   0689816 .