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

Эквивалентное определение — если любой цикл без хорд имеет максимум три ребра. Другими словами, хордальный граф — это граф без порождённых циклов длины более чем три.

Хордальные графы являются подмножеством совершенных графов . Они также иногда называются циклически жёсткими графами или триангулированными графами . (Последний термин иногда ошибочно используют для планарной триангуляции. См. максимальные планарные графы .)

Совершенное исключение и эффективное распознавание хордальных графов

Совершенный порядок исключения в графе — это порядок вершин графа, такой, что для каждой вершины v , v и соседи v , находящиеся после v в упорядочении, образуют клику . Граф хордален тогда и только тогда, когда имеет совершенный порядок исключения

Роуз, Люкер и Тарьян (1976) (см. также Хабиб, Макконнел, Пауль, Вьенно (2000) ) показали, что совершенный порядок исключения хордального графа можно эффективно найти с помощью алгоритма, известного как лексикографический поиск в ширину . Этот алгоритм осуществляет разделение вершин графа в последовательность множеств. Изначально последовательность состоит из единственного набора, содержащего все вершины. Алгоритм в цикле выбирает вершину v из самого старого множества в последовательности, содержащего ещё не выбранные вершины, и делит каждое множество S последовательности на два меньших — одно состоит из соседей вершины v в S , в другое попадают все оставшиеся вершины. Когда процесс деления будет проведён для всех вершин, все множества последовательности содержат по одной вершине и образуют последовательность, обратную совершенному порядку исключения.

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

Множество всех совершенных порядков исключения хордального графа можно рассматривать как базовые слова . Чандран и соавторы использовали эту связь с антиматроидами как часть алгоритма для эффективного перечисления всех совершенных порядков исключения для заданного хордального графа.

Наибольшие клики и раскраска графа

Ещё одно приложение для совершенного порядка исключения — это поиск максимальной клики хордального графа за полиномиальное время, в то время как для графов общего вида та же самая задача является NP-полной (хордальный граф может иметь лишь линейно много наибольших клик , в то время как нехордальные графы могут иметь их экспоненциально много). Для того, чтобы получить список всех наибольших клик хордального графа, достаточно найти совершенный порядок исключения, построить клику для каждой вершины v из всех соседних вершин, идущих в порядке после v , и проверить, является ли полученная клика наибольшей.

Наибольшая клика, имеющая максимальный размер, — это максимальная клика и, поскольку хордальные графы совершенны, размер этой клики равен хроматическому числу хордального графа. Хордальные графы являются вполне упорядочиваемыми — оптимальную раскраску можно получить с помощью алгоритма жадной раскраски , взяв вершины в обратном к совершенному исключению порядке.

Минимальные сепараторы

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

Семейство хордальных графов может быть определено как множество графов, вершины которых можно разделить на три непустых подмножества A , S , и B , таких что A ∪ S и S ∪ B оба образуют хордальные порождённые подграфы , S является кликой, и нет рёбер, связывающих A и B . Таким образом, это графы, которые допускают рекурсивное разбиение на меньшие подграфу с помощью клик. По этой причине хордальные графы иногда называют разложимыми графами .

Пересечение графов поддеревьев

Другая характеристика хордальных графов использует деревья и их поддеревья.

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

Представление хордальных графов как граф пересечений поддеревьев образует разложение графа на деревья с древесной шириной на единицу меньшей размера самой большой клики графа. Разложение любого графа G на деревья может рассматриваться как представление графа G в качестве подграфа хордального графа. Разложение графа на деревья является также деревом объединения в алгоритме распространения доверия .

Связь с другими классами графов

Подклассы

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

Расщепляемые графы одновременно и сами хордальны, и являются дополнениями хордальных графов. Бендер, Ричмонд и Уормальд (1985) показали, что при стремлении n к бесконечности доля хордальных графов с n вершинами, являющихся расщепляемыми, стремится к единице.

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

Строго хордальные графы — это графы, являющиеся хордальными и не содержащие n-солнце ( n ≥3) в качестве порождённых подграфов.

K-деревья — это хордальные графы, у которых все наибольшие клики и максимальные сепараторы клик имеют один и тот же размер. Графы Аполлония — это хордальные максимальные планарные графы , или, что эквивалентно, планарные 3-деревья. Максимальные внешнепланарные графы — это подкласс 2-деревьев, а потому они тоже хордальны.

Суперклассы

Хордальные графы являются подклассом хорошо известных совершенных графов . Другие суперклассы хордальных графов включают слабые хордальные графы, графы без нечётных дыр, и . Фактически хордальные графы — это в точности графы, одновременно без чётных дыр и без нечётных дыр (см. дыра в теории графов).

Любой хордальный граф является сжатым , то есть графом, у которого любой периферийный цикл является треугольником, поскольку периферийные циклы являются специальным случаем порождённого цикла. Сжатые графы могут быть образованы суммами по кликам хордальных графов и максимальных хордальных графов. Таким образом, сжатые графы включают максимальные планарные графы .

Примечания

Литература

• Martin Charles Golumbic. . — Academic Press, 1980. .

Ссылки

• :
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .