В математической области теории графов хордальный граф — это граф, в котором все циклы из четырёх или более вершин имеют хорду , которая является ребром , не являющимся частью цикла, но соединяющим две вершины цикла. Эквивалентно, каждый индуцированный цикл в графе должен иметь ровно три вершины. Хордовые графы также могут быть охарактеризованы как графы, имеющие совершенные упорядочения исключения, как графы, в которых каждый минимальный сепаратор является кликой , и как графы пересечений поддеревьев дерева. Иногда их также называют жёсткими графами цепей [1] или триангулированными графами : [2] хордовое завершение графа обычно называется триангуляцией этого графа.
Хордовые графы являются подмножеством идеальных графов . Они могут быть распознаны за линейное время , и несколько проблем, которые сложны для других классов графов, таких как раскраска графа, могут быть решены за полиномиальное время, когда входные данные являются хордовыми. Древовидная ширина произвольного графа может быть охарактеризована размером клик в хордовых графах, которые его содержат.
Совершенный порядок исключения в графе — это упорядочение вершин графа, при котором для каждой вершины v , v и соседи v , которые встречаются после v в порядке, образуют клику . Граф является хордальным тогда и только тогда, когда он имеет совершенный порядок исключения. [3]
Rose, Lueker & Tarjan (1976) (см. также Habib et al. 2000) показывают, что идеальный порядок исключения хордового графа может быть эффективно найден с помощью алгоритма, известного как лексикографический поиск в ширину . Этот алгоритм поддерживает разбиение вершин графа на последовательность множеств; изначально эта последовательность состоит из одного множества со всеми вершинами. Алгоритм многократно выбирает вершину v из самого раннего множества в последовательности, которое содержит ранее не выбранные вершины, и разбивает каждое множество S последовательности на два меньших подмножества, первое из которых состоит из соседей v в S , а второе — из не-соседей. Когда этот процесс разделения был выполнен для всех вершин, последовательность множеств имеет одну вершину на множество, в обратном порядке совершенного исключения.
Поскольку и этот процесс поиска в ширину, и процесс проверки того, является ли упорядочение идеальным исключением, могут быть выполнены за линейное время , можно распознавать хордовые графы за линейное время. Задача сэндвича с графом на хордовых графах является NP-полной [4], тогда как задача зондового графа на хордовых графах имеет полиномиальную сложность. [5]
Множество всех совершенных упорядочений исключения хордового графа можно смоделировать как базовые слова антиматроида ; Чандра и др. (2003) используют эту связь с антиматроидами как часть алгоритма для эффективного перечисления всех совершенных упорядочений исключения заданного хордового графа.
Другое применение упорядочений совершенного исключения — нахождение максимальной клики хордового графа за полиномиальное время, в то время как та же проблема для общих графов является NP-полной . В более общем случае хордовый граф может иметь только линейно много максимальных клик , в то время как нехордовые графы могут иметь экспоненциально много. Это означает, что класс хордовых графов имеет мало клик . Чтобы составить список всех максимальных клик хордового графа, просто найдите упорядочение совершенного исключения, сформируйте клику для каждой вершины v вместе с соседями v , которые находятся позже v в упорядочении совершенного исключения, и проверьте, является ли каждая из полученных клик максимальной.
Графы клик хордовых графов являются дуально хордовыми графами . [6]
Наибольшая максимальная клика является максимальной кликой, и, поскольку хордовые графы являются совершенными, размер этой клики равен хроматическому числу хордового графа. Хордовые графы являются совершенно упорядочиваемыми : оптимальная раскраска может быть получена путем применения жадного алгоритма раскраски к вершинам в обратном порядке совершенного исключения. [7]
Хроматический многочлен хордового графа легко вычислить. Найдите идеальный порядок исключения v 1 , v 2 , …, v n . Пусть N i равно количеству соседей v i , которые идут после v i в этом порядке. Например, N n = 0 . Хроматический многочлен равен (последний множитель — это просто x , поэтому x делит многочлен, как и должно быть.) Очевидно, что это вычисление зависит от хордальности. [8]
В любом графе разделитель вершин — это множество вершин, удаление которых делает оставшийся граф несвязным; разделитель минимален, если у него нет собственного подмножества, которое также является разделителем. Согласно теореме Дирака (1961), хордовые графы — это графы, в которых каждый минимальный разделитель является кликой; Дирак использовал эту характеристику, чтобы доказать, что хордовые графы совершенны .
Семейство хордовых графов может быть определено индуктивно как графы, вершины которых можно разделить на три непустых подмножества A , S и B , так что и оба образуют хордовые индуцированные подграфы , S является кликой и нет ребер из A в B . То есть, это графы, которые имеют рекурсивное разложение с помощью разделителей клик на меньшие подграфы. По этой причине хордовые графы также иногда называют разложимыми графами . [9]
Альтернативная характеристика хордовых графов, предложенная Гаврилом (1974), включает деревья и их поддеревья.
Из набора поддеревьев дерева можно определить граф поддерева , который является графом пересечений , имеющим одну вершину на поддерево и ребро, соединяющее любые два поддерева, которые пересекаются в одном или нескольких узлах дерева. Гаврил показал, что графы поддеревьев являются в точности хордовыми графами.
Представление хордового графа как пересечения поддеревьев образует древовидную декомпозицию графа с древовидной шириной , на единицу меньшей размера наибольшей клики в графе; древовидная декомпозиция любого графа G может рассматриваться таким образом как представление G как подграфа хордового графа. Древовидная декомпозиция графа также является деревом соединений алгоритма дерева соединений .
Интервальные графы — это графы пересечений поддеревьев графов путей , частный случай деревьев. Поэтому они являются подсемейством хордовых графов.
Расщепляемые графы — это графы, которые являются как хордовыми, так и дополнениями хордовых графов. Бендер, Ричмонд и Вормальд (1985) показали, что в пределе, когда n стремится к бесконечности, доля расщепляемых хордовых графов с n вершинами стремится к единице.
Графы Птолемея — это графы, которые являются как хордовыми, так и дистанционно наследуемыми . Квазипогороговые графы — это подкласс графов Птолемея, которые являются как хордовыми, так и кографами . Графы блоков — это еще один подкласс графов Птолемея, в которых каждые две максимальные клики имеют не более одной общей вершины. Особый тип — графы-мельницы , где общая вершина одна и та же для каждой пары клик.
Сильно хордальные графы — это графы, которые являются хордальными и не содержат n -солнца (для n ≥ 3 ) в качестве индуцированного подграфа. Здесь n -солнце — это n -вершинный хордовый граф G вместе с набором из n вершин степени два, смежных с ребрами гамильтонова цикла в G .
K -деревья — это хордовые графы, в которых все максимальные клики и все разделители максимальных клик имеют одинаковый размер. [10] Аполлоновские сети — это хордовые максимальные планарные графы или, что эквивалентно, планарные 3-деревья. [10] Максимальные внешнепланарные графы являются подклассом 2-деревьев и, следовательно, также являются хордовыми.
Хордовые графы являются подклассом хорошо известных совершенных графов . Другие суперклассы хордовых графов включают слабо хордовые графы, графы cop-win , графы без нечетных дыр, графы без четных дыр и графы Мейниэля . Хордовые графы — это как раз те графы, которые являются как нечетными, так и четными дырами (см. дыры в теории графов).
Каждый хордовый граф является сжатым графом , графом, в котором каждый периферийный цикл является треугольником, поскольку периферийные циклы являются частным случаем индуцированных циклов. Сжатые графы являются графами, которые могут быть образованы кликовыми суммами хордовых графов и максимальных планарных графов. Следовательно, сжатые графы включают максимальные планарные графы . [11]
Если G — произвольный граф, хордовое завершение G (или минимальное заполнение ) — это хордовый граф, содержащий G в качестве подграфа. Параметризованная версия минимального заполнения является фиксированно параметрически разрешимой и , более того, разрешима за параметризованное субэкспоненциальное время. [12] [ 13] Древесная ширина G на единицу меньше числа вершин в максимальной клике хордового завершения, выбранного для минимизации размера этой клики. K -деревья — это графы, к которым нельзя добавить дополнительные ребра, не увеличив их древесную ширину до числа, большего, чем k . Следовательно, k -деревья являются своими собственными хордовыми завершениями и образуют подкласс хордовых графов. Хордовые завершения также могут быть использованы для характеристики нескольких других связанных классов графов. [14]
