Хордальный граф

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

Цикл (чёрный) с двумя хордами (зелёные). Граф хордален. Удаление любого зелёного ребра приведёт к потере хордальности. В этом случае оставшееся зелёное ребро вместе с тремя чёрными рёбрами образует цикл длины четыре без хорд.

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

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

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

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

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

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

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

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

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

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

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

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

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

Пересечение графов поддеревьев
Хордальный граф с восемью вершинами, представленный в виде пересечения восьми поддеревьев дерева, содержащего шесть вершин.

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

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

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

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

Подклассы

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

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

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

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

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

Суперклассы

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

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

Примечания
  1. G. A. Dirac. On rigid circuit graphs // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1961. — Т. 25. — С. 71–76. — doi:10.1007/BF02992776..
  2. Weisstein, Eric W. Triangulated Graph (англ.) на сайте Wolfram MathWorld.
  3. D. R. Fulkerson, O. A. Gross. Incidence matrices and interval graphs // Pacific J. Math. — 1965. — Т. 15. — С. 835–855..
  4. D. Rose, George Lueker, Robert E. Tarjan. Algorithmic aspects of vertex elimination on graphs // SIAM Journal on Computing. — 1976. — Т. 5, вып. 2. — С. 266–283. — doi:10.1137/0205021..
  5. Michel Habib, Ross McConnell, Christophe Paul, Laurent Viennot. Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing // Theoretical Computer Science. — 2000. — Т. 234. — С. 59–84. — doi:10.1016/S0304-3975(97)00241-7..
  6. H. L. Bodlaender, M. R. Fellows, T. J. Warnow. Two strikes against perfect phylogeny // Proc. of 19th International Colloquium on Automata Languages and Programming. — 1992..
  7. Anne Berry, Martin Charles Golumbic, Marina Lipshteyn. Recognizing chordal probe graphs and cycle-bicolorable graphs // SIAM Journal on Discrete Mathematics. — 2007. — Т. 21, вып. 3. — С. 573–591. — doi:10.1137/050637091..
  8. L. S. Chandran, L. Ibarra, F. Ruskey, J. Sawada. Enumerating and characterizing the perfect elimination orderings of a chordal graph // Theoretical Computer Science. — 2003. — Т. 307, вып. 2. — С. 303–317. — doi:10.1016/S0304-3975(03)00221-4..
  9. Frédéric Maffray. Recent Advances in Algorithms and Combinatorics / editors: Bruce A. Reed, Cláudia L. Sales. — Springer-Verlag, 2003. — Т. 11. — С. 65–84. — (CMS Books in Mathematics). — ISBN 0-387-95434-1. — doi:10.1007/0-387-22444-0_3..
  10. Peter Bartlett. Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations:.
  11. Fănică Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs // Издание of Combinatorial Theory, Series B. — 1974. — Т. 16. — С. 47–56. — doi:10.1016/0095-8956(74)90094-X..
  12. E. A. Bender, L. B. Richmond, N. C. Wormald. Almost all chordal graphs split // J. Austral. Math. Soc.. — 1985. — Т. 38, вып. 2. — С. 214–221. — doi:10.1017/S1446788700023077..
  13. H. P. Patil. On the structure of k-trees // Издание of Combinatorics, Information and System Sciences. — 1986. — Т. 11, вып. 2–4. — С. 57–64..
  14. P. D. Seymour, R. W. Weaver. A generalization of chordal graphs // Издание of Graph Theory. — 1984. — Т. 8, вып. 2. — С. 241–251. — doi:10.1002/jgt.3190080206..

Литература
  • Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980..

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.