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