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