Хордальный граф
В математической области теории графов хордовый граф — это граф , в котором все циклы из четырех или более вершин имеют хорду , которая является ребром , не являющимся частью цикла, но соединяющим две вершины цикла. Эквивалентно, каждый индуцированный цикл в графе должен иметь ровно три вершины. Хордовые графы также могут быть охарактеризованы как графы с совершенным порядком исключения, как графы, в которых каждый минимальный разделитель является кликой, и как графы пересечений поддеревьев дерева. Иногда их также называют графами жестких схем [1] или триангулированные графики . [2]
Хордальные графы являются подмножеством совершенных графов . Их можно распознать за линейное время , а некоторые проблемы, которые сложны для других классов графов, такие как раскраска графа , могут быть решены за полиномиальное время, когда входные данные являются хордальными. Древовидная ширина произвольного графа может быть охарактеризована размером клик хордовых графов, которые его содержат.
Совершенный порядок исключения в графе — это такой порядок вершин графа, что для каждой вершины v , v и соседи v , которые встречаются после v в порядке, образуют клику . Граф является хордальным тогда и только тогда, когда он имеет совершенный порядок исключения. [3]
Rose, Lueker & Tarjan (1976) (см. также Habib et al. 2000 ) показывают, что совершенный порядок исключения хордового графа может быть эффективно найден с помощью алгоритма, известного как лексикографический поиск в ширину . Этот алгоритм поддерживает разделение вершин графа на последовательность наборов; изначально эта последовательность состоит из одного множества со всеми вершинами. Алгоритм многократно выбирает вершину v из самого раннего набора в последовательности, которая содержит ранее невыбранные вершины, и разбивает каждое множество S последовательности на два меньших подмножества, первое из которых состоит из соседей v в Sа второй состоит из не-соседей. Когда этот процесс разделения был выполнен для всех вершин, последовательность наборов имеет одну вершину на набор, в обратном порядке идеального исключения.
Поскольку и этот лексикографический процесс поиска в ширину, и процесс проверки того, является ли упорядочение идеальным порядком исключения, могут выполняться за линейное время, можно распознавать хордовые графы за линейное время. Задача сэндвич-графа на хордовых графах является NP-полной [4] , тогда как задача о пробном графе на хордовых графах имеет полиномиальную сложность. [5]
Набор всех совершенных порядков исключения хордового графа может быть смоделирован как основные слова антиматроида ; Чандран и др. (2003) используют эту связь с антиматроидами как часть алгоритма для эффективного перечисления всех совершенных порядков исключения данного хордового графа.
