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

Цикл (черный) с двумя аккордами (зеленый). Что касается этой части, то граф хордальный. Однако удаление одного зеленого ребра приведет к получению нехордального графа. Действительно, другое зеленое ребро с тремя черными ребрами образует цикл длиной четыре без хорд.

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

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

Идеальное устранение и эффективное распознавание

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

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

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

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

Максимальные клики и раскраска графов

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

Графы клик хордальных графов являются двойственно хордальными графами .

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

Хроматический полином хордального графа легко вычислить. Найдите идеальный порядок исключения v ₁ , v ₂ , …, v _n . Пусть N _i равно числу соседей v _i , которые идут после vi _{в этом порядке} . Например, N _n = 0 . Хроматический многочлен равен $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ (Последний множитель — это просто x , поэтому x делит полином, как и должно быть.) Очевидно, что это вычисление зависит от хордовости.

Минимальные разделители

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

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

Графы пересечений поддеревьев

Хордальный граф с восемью вершинами, представленный как граф пересечений восьми поддеревьев шестиузлового дерева.

Альтернативная характеристика хордальных графов, предложенная Гаврилом (1974) , включает деревья и их поддеревья.

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

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

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

Подклассы

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

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

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

Сильно хордальные графы — это хордальные графы, не содержащие n -солнц (при n ≥ 3 ) в качестве индуцированного подграфа. Здесь n -солнце — это n -вершинный хордальный граф G вместе с набором из n вершин второй степени, смежных с рёбрами гамильтонова цикла в G .

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

Суперклассы

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

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

Хордальные завершения и ширина дерева

Основная статья: Хордальное завершение

Если G — произвольный граф, хордальное завершение G G (или минимальное заполнение ) — это хордальный граф, который содержит в качестве подграфа. Параметризованная версия минимального заполнения имеет фиксированный параметр и, более того, разрешима за параметризованное субэкспоненциальное время. Ширина дерева G . на единицу меньше числа вершин в максимальной клике хордального завершения, выбранного для минимизации размера этой клики — K -деревья это графы, к которым нельзя добавить никакие дополнительные ребра без увеличения ширины их дерева до числа, большего k .Следовательно, k -деревья являются собственными хордальными пополнениями и образуют подкласс хордальных графов. Хордальные пополнения также можно использовать для характеристики некоторых других родственных классов графов.

Ссылки

• Агнарссон, Гейр (2003), «О хордальных графах и их хроматических полиномах» , Mathematica Scandinavica , 93 (2): 240–246, doi : 10.7146/math.scand.a-14421 , MR   2009583 .
• Бендер, Е.А.; Ричмонд, LB; Вормальд, Северная Каролина (1985), «Почти все хордальные графы расщепляются», J. Austral. Математика. Соц. , А, 38 (2): 214–221, doi : 10.1017/S1446788700023077 , MR   0770128 .
• Берж, Клод (1967), «Некоторые классы совершенных графов», в Харари, Франк (ред.), Теория графов и теоретическая физика , Academic Press, стр. 155–165, MR   0232694 .
• Берри, Энн; Голумбик, Мартин Чарльз ; Липштейн, Марина (2007), «Распознавание хордальных пробных графов и циклически двухцветных графов», SIAM Journal on Discrete Mathematics , 21 (3): 573–591, doi : 10.1137/050637091 .
• Бодлендер, HL ; Товарищи, MR ; Варноу, Т.Дж. (1992), «Два удара по идеальной филогении» (PDF) , Proc. 19-го Международного коллоквиума по языкам автоматов и программированию , Конспекты лекций по информатике, том. 623, стр. 273–283, doi : 10.1007/3-540-55719-9_80 , hdl : 1874/16653 .
• Чандран, Л.С.; Ибарра, Л.; Раски, Ф .; Савада, Дж. (2003), «Перечисление и характеристика идеальных порядков исключения хордального графа» (PDF) , Theoretical Computer Science , 307 (2): 303–317, doi : 10.1016/S0304-3975(03)00221- 4 .
• Дирак, Джорджия (1961), «О графах жестких цепей», Статьи математического семинара Гамбургского университета , 25 (1–2): 71–76, doi : 10.1007/BF02992776 , MR   0130190 , S2CID   120608513 .
• Фомин Федор Владимирович; Виллангер, Ингве (2013), «Субэкспоненциальный параметризованный алгоритм для минимального заполнения», SIAM J. Comput. , 42 (6): 2197–2216, arXiv : 1104.2230 , doi : 10.1137/11085390X , S2CID   934546 .
• Фулкерсон, Др. ; Гросс, О.А. (1965), «Матрицы заболеваемости и интервальные графики» , Pacific J. Math. , 15 (3): 835–855, doi : 10.2140/pjm.1965.15.835 .
• Гаврил, Фаника (1974), «Графы пересечений поддеревьев в деревьях являются в точности хордальными графами», Journal of Combinatorial Theory , Series B, 16 : 47–56, doi : 10.1016/0095-8956(74)90094-X .
• Голумбик, Мартин Чарльз (1980), Алгоритмическая теория графов и совершенные графы , Academic Press .
• Хабиб, Мишель; МакКоннелл, Росс; Пол, Кристоф; Вьенно, Лоран (2000), «Lex-BFS и уточнение разделов с приложениями к транзитивной ориентации, распознаванию интервальных графов и последовательному тестированию» , Theoretical Computer Science , 234 (1–2): 59–84, doi : 10.1016/ С0304-3975(97)00241-7 .
• Каплан, Хаим; Шамир, Рон; Тарьян, Роберт (1999), «Разрешимость параметризованных задач завершения на хордальных, строго хордальных и правильных интервальных графах», SIAM J. Comput. , 28 (5): 1906–1922, номер документа : 10.1137/S0097539796303044 .
• Маффрэ, Фредерик (2003), «О раскраске идеальных графов», Рид, Брюс А .; Продажи, Клаудия Л. (ред.), «Последние достижения в области алгоритмов и комбинаторики» , Книги CMS по математике, том. 11, Springer-Verlag, стр. 65–84, номер документа : 10.1007/0-387-22444-0_3 , ISBN.  0-387-95434-1 .
• Парра, Андреас; Шеффлер, Петра (1997), «Характеристики и алгоритмические применения вложений хордальных графов», Discrete Applied Mathematics , 79 (1–3): 171–188, doi : 10.1016/S0166-218X(97)00041-3 , MR   1478250 .
• Патил, HP (1986), «О структуре k -деревьев», Журнал комбинаторики, информации и системных наук , 11 (2–4): 57–64, MR   0966069 .
• Роуз, Дональд Дж. (декабрь 1970 г.), «Триангулированные графики и процесс исключения», Journal of Mathematical Analysis and Applications , 32 (3): 597–609, doi : 10.1016/0022-247x(70)90282-9
• Роуз, Д.; Люкер, Джордж; Тарьян, Роберт Э. (1976), «Алгоритмические аспекты исключения вершин на графах», SIAM Journal on Computing , 5 (2): 266–283, doi : 10.1137/0205021 , MR   0408312 .
• Сеймур, Полиция ; Уивер, Р.В. (1984), «Обобщение хордальных графов», Журнал теории графов , 8 (2): 241–251, doi : 10.1002/jgt.3190080206 , MR   0742878 .
• Шварцфитер, JL ; Борнштейн, К.Ф. (1994), «Кликовые графы хордальных и траекторных графов», SIAM Journal on Discrete Mathematics , 7 (2): 331–336, doi : 10.1137/s0895480191223191 , hdl : 11422/1497 .

Внешние ссылки

• Информационная система по включению классов графов : хордальный граф
• Вайсштейн, Эрик В. «Хордальный граф» . Математический мир .