Введение
Граф, в котором все длинные циклы имеют хорду. В математической области теории графов, хордальный граф – это граф, в котором все циклы длиной четыре или более имеют хорду, то есть ребро, не входящее в цикл, но соединяющее две его вершины. Эквивалентно, любой индуцированный цикл в графе должен содержать ровно три вершины. Хордальные графы также могут быть охарактеризованы как графы, имеющие совершенный порядок удаления вершин, как графы, в которых каждый минимальный разделитель является кликой, и как графы пересечений поддеревьев дерева. Их иногда также называют жесткими цепными графами или триангулированными графами: хордальное дополнение графа обычно называют триангуляцией этого графа. Хордальные графы являются подмножеством совершенных графов. Их можно распознать за линейное время, и некоторые задачи, сложные для других классов графов, такие как раскраска графа, могут быть решены за полиномиальное время, если на вход подан хордальный граф. Древесная ширина произвольного графа может быть охарактеризована размером клик в хордальных графах, содержащих его.
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs: a chordal completion of a graph is typically called a triangulation of that graph. Chordal graphs are a subset of the perfect graphs. They may be recognized in linear time, and several problems that are hard on other classes of graphs such as graph coloring may be solved in polynomial time when the input is chordal. The treewidth of an arbitrary graph may be characterized by the size of the cliques in the chordal graphs that contain it.
Совершенная ликвидация и эффективное распознавание
Порядок совершенного исключения в графе — это упорядочение вершин графа, такое что для каждой вершины v, вершина v и соседи v, которые следуют за v в этом упорядочении, образуют клику. Граф является хордальным тогда и только тогда, когда у него существует порядок совершенного исключения. (см. также) Докажите, что порядок совершенного исключения хордального графа можно эффективно найти с помощью алгоритма, известного как лексикографический поиск в ширину. Этот алгоритм поддерживает разбиение вершин графа на последовательность множеств; изначально эта последовательность состоит из одного множества, содержащего все вершины. Алгоритм многократно выбирает вершину v из самого первого множества в последовательности, содержащего ранее невыбранные вершины, и разделяет каждое множество S последовательности на два меньших подмножества: первое состоит из соседей v в S, а второе — из не-соседей. Когда этот процесс разделения завершен для всех вершин, последовательность множеств содержит по одной вершине в каждом множестве, в порядке, обратном порядку совершенного исключения. Поскольку как этот процесс лексикографического поиска в ширину, так и процесс проверки, является ли упорядочение порядком совершенного исключения, могут быть выполнены за линейное время, можно распознавать хордальные графы за линейное время. Задача о "граф-сэндвиче" на хордальных графах является NP-полной, в то время как задача о "граф-зондировании" на хордальных графах имеет полиномиальную сложность. Множество всех порядков совершенного исключения хордального графа можно представить в виде основных слов антиматроида; используйте эту связь с антиматроидами как часть алгоритма для эффективного перечисления всех порядков совершенного исключения заданного хордального графа.
Максимальные группы и окраска графа
Еще одно применение порядков совершенного исключения — нахождение максимальной клики хордального графа за полиномиальное время, в то время как та же задача для общих графов является NP-полной. В более общем случае, хордальный граф может иметь лишь линейное количество максимальных клик, тогда как нехордальные графы могут иметь экспоненциальное количество. Это подразумевает, что класс хордальных графов характеризуется небольшим числом клик. Чтобы перечислить все максимальные клики хордального графа, достаточно найти порядок совершенного исключения, сформировать клику для каждой вершины v вместе с соседями v, которые следуют за v в этом порядке, и проверить, является ли каждая из полученных клик максимальной. Графы клик хордальных графов являются дуально хордальными графами. Наибольшая максимальная клика является максимальной кликой, и, поскольку хордальные графы являются совершенными, размер этой клики равен хроматическому числу хордального графа. Хордальные графы допускают совершенное упорядочение: оптимальную раскраску можно получить, применив жадный алгоритм раскраски к вершинам в порядке, обратном порядку совершенного исключения. Хроматический полином хордального графа легко вычислить. Найдите порядок совершенного исключения. Пусть обозначает количество соседей вершины , которые следуют за в этом порядке. Например, . Хроматический полином равен (Последний множитель — просто x, поэтому x делит полином, что и ожидается.) Очевидно, что это вычисление зависит от хордальности.
Минимальные сепараторы
В любом графе разделителем вершин является множество вершин, удаление которых приводит к разъединению оставшегося графа; разделитель называется минимальным, если у него нет собственного подмножества, являющегося также разделителем. Согласно теореме, хордальные графы – это графы, в которых каждый минимальный разделитель является кликой; Дирак использовал эту характеристику для доказательства того, что хордальные графы являются совершенными. Семейство хордальных графов можно определить индуктивно как графы, вершины которых можно разделить на три непустых подмножества A, S и B, такие что A ∪ S и S ∪ B образуют хордальные индуцированные подграфы, S является кликой и нет рёбер между A и B. Иными словами, это графы, имеющие рекурсивное разложение по кликовым разделителям на меньшие подграфы. По этой причине хордальные графы также иногда называют разложимыми графами.
Графики пересечения поддеревьев
Альтернативная характеристика хордальных графов, предложенная , основана на деревьях и их поддеревьях. Из набора поддеревьев дерева можно построить граф поддеревьев, который является графом пересечений, имеющим по вершине для каждого поддерева и ребро, соединяющее любые два поддерева, которые имеют общие вершины в дереве. Гавриль показал, что графы поддеревьев являются точно хордальными графами. Представление хордального графа в виде пересечения поддеревьев формирует древесное разложение графа, ширина которого равна на единицу меньше размера наибольшей клики в графе; древесное разложение любого графа G можно рассматривать таким образом как представление G в виде подграфа хордального графа. Дерево разложения графа также является деревом соединений алгоритма дерева соединений.
Подклассы
Интервальные графы — это графики пересечения поддеревьев графов путей, являющиеся частным случаем деревьев. Следовательно, они представляют собой подсемейство хордальных графов. Разделенные графы — это графы, которые одновременно являются хордальными и комплементами хордальных графов. Показано, что в пределе при n стремящемся к бесконечности доля n-вершинных хордальных графов, являющихся разделенными, стремится к единице. Птолемеевы графы — это графы, которые одновременно являются хордальными и дистанционно наследственными. Квазипороговые графы — это подкласс птолемеевых графов, которые одновременно являются хордальными и кографами. Блочные графы — это еще один подкласс птолемеевых графов, в котором каждые две максимальные клики имеют не более одной общей вершины. Особым типом являются графы-ветряные мельницы, где общая вершина одинакова для каждой пары клик. Строго хордальные графы — это графы, которые являются хордальными и не содержат n sun (при n ≥ 3) в качестве индуцированного подграфа. Здесь n sun — это n-вершинный хордальный граф G вместе с набором из n вершин степени два, смежных с ребрами гамильтонова цикла в G. K-деревья — это хордальные графы, в которых все максимальные клики и все максимальные сепараторы клик имеют одинаковый размер. Аполлоновы сети — это хордальные максимальные планарные графы, или, эквивалентно, планарные 3-деревья. Максимальные внешнепланарные графы являются подклассом 2-деревьев и, следовательно, также являются хордальными.
K trees are chordal graphs in which all maximal cliques and all maximal clique separators have the same size. Apollonian networks are chordal maximal planar graphs, or equivalently planar 3 trees. Maximal outerplanar graphs are a subclass of 2 trees, and therefore are also chordal.
Суперклассы
Хордальные графы являются подклассом хорошо известных совершенных графов. Другие суперклассы хордальных графов включают слабохордальные графы, графы типа cop-win, графы без нечётных циклов нечётной длины, графы без чётных циклов чётной длины и графы Мейниеля. Хордальные графы — это графы, которые не содержат ни циклов нечётной длины, ни циклов чётной длины (см. циклы в теории графов). Каждый хордальный граф является странгулированным графом, то есть графом, в котором каждый периферический цикл является треугольником, поскольку периферические циклы являются частным случаем индуцированных циклов. Странгулированные графы — это графы, которые можно получить путём суммирования клик хордальных графов и максимальных планарных графов. Следовательно, странгулированные графы включают в себя максимальные планарные графы.
Кордальные завершения и ширина дерева
Если G – произвольный граф, то хордальное завершение G (или минимальное заполнение) – это хордальный граф, содержащий G в качестве подграфа. Параметризованная версия задачи о минимальном заполнении допускает эффективное решение при фиксированных параметрах и, более того, разрешима за параметризованное субекспоненциальное время. Древесная ширина графа G на единицу меньше числа вершин в максимальной клике хордального завершения, выбранного для минимизации размера этой клики. k-деревья – это графы, к которым нельзя добавить ребро, не увеличив их древесную ширину до значения, превышающего k. Следовательно, k-деревья являются собственными хордальными завершениями и образуют подкласс хордальных графов. Хордальные завершения также могут быть использованы для характеризации нескольких других связанных классов графов.
Therefore, the k trees are their own chordal completions, and form a subclass of the chordal graphs. Chordal completions can also be used to characterize several other related classes of graphs.