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