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