Идеально упорядочиваемый график - Perfectly orderable graph

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

Определение

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

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

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

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

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

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

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

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

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

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

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

Примечания

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

Рекомендации