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

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

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

Идеальное исключение и эффективное распознавание [ править ]

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

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

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

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

Максимальные клики и раскраска графа [ править ]

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

В клике графой из аккордовых графов являются двойственно Хордовыми графиками . [6]

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

Хроматический многочлен из хорд графа легко вычислить. Найдите идеальный порядок исключения. Пусть N i равно количеству соседей v i, которые идут после v i в этом порядке. Например, N n  = 0. Хроматический многочлен равен (последний множитель - это просто x , поэтому x делит многочлен, как и должно быть.) Ясно, что это вычисление зависит от хордальности. [8]

Минимальные разделители [ править ]

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

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

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

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

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

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

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

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

Подклассы [ править ]

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

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

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

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

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

Суперклассы [ править ]

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

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

Хордовые окончания и ширина дерева [ править ]

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

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

Заметки [ править ]

  1. ^ Дирак (1961) .
  2. Перейти ↑ Berge (1967) .
  3. ^ Фулкерсон и Гросс (1965) .
  4. ^ Bodlaender, Fellows & Warnow (1992) .
  5. ^ Berry, Golumbic & Lipshteyn (2007) .
  6. ^ Szwarcfiter & Борнстейн (1994) .
  7. ^ Maffray (2003) .
  8. ^ Например, Агнарссон (2003) , замечание 2.5, называет этот метод хорошо известным.
  9. ^ Питер Бартлетт. «Ненаправленные графические модели: хордовые графы, разлагаемые графы, деревья соединений и факторизации» (PDF) .
  10. ^ а б Патил (1986) .
  11. ↑ Сеймур и Уивер (1984) .
  12. Перейти ↑ Kaplan, Shamir & Tarjan (1999) .
  13. ^ Фомин & Villanger (2013) .
  14. ^ Парра и Шеффлер (1997) .

Ссылки [ править ]

  • Agnarsson Гейр (2003), "О аккордовых графов и их хроматические многочлены" , Mathematica Scandinavica , 93 (2): 240-246, DOI : 10,7146 / math.scand.a-14421 , MR  2009583.
  • Бендер, Э.А.; Ричмонд, LB; Wormald, NC (1985), «Почти все хордовые графы расщепляются», J. Austral. Математика. Soc. , А, 38 (2): 214-221, DOI : 10,1017 / S1446788700023077 , МР  0770128.
  • Берже, Клод (1967), «Некоторые классы совершенных графов», в Харари, Франк (редактор), Теория графов и теоретическая физика , Academic Press, стр. 155–165, MR  0232694.
  • Берри, Энн; Голумбик, Мартин Чарльз ; Липштейн, Марина (2007), «Распознавание хордовых пробных графов и циклических двухцветных графов», Журнал SIAM по дискретной математике , 21 (3): 573–591, doi : 10.1137 / 050637091.
  • Bodlaender, HL ; Стипендиаты, MR ; Warnow, TJ (1992), "Два удара по совершенной филогении" (PDF) , Proc. 19 - й Международный коллоквиум по автоматных языков и программирования , Lecture Notes в области компьютерных наук, 623 ., С. 273-283, DOI : 10.1007 / 3-540-55719-9_80 , ЛВП : 1874/16653.
  • Чандран, LS; Ibarra, L .; Раски, Ф .; Sawada, J. (2003), "Enumerating и характеризующее идеальные отборочные упорядочения в хорде графы" (PDF) , теоретическая информатика , 307 (2): 303-317, DOI : 10.1016 / S0304-3975 (03) 00221- 4.
  • Дирака, Г. А. (1961), "О жестких графиков цепи" (PDF) , Abhandlungen AUS DEM Mathematischen семинар - дер - Universität Hamburg , 25 (1-2): 71-76, DOI : 10.1007 / BF02992776 , МР  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.
  • Гаврила, Fănică (1974), "Пересечение графиков поддеревьев на деревьях точно хордовой диаграммы", Журнал комбинаторной теории , серии B, 16 : 47-56, DOI : 10,1016 / 0095-8956 (74) 90094-X.
  • Голумбик, Мартин Чарльз (1980), теория алгоритмических графов и совершенные графы , Academic Press.
  • Хабиб, Мишель; МакКоннелл, Росс; Пол, Кристоф; Viennot, Лоран (2000), "Lex-BFS и уточнение раздела, с приложениями к переходной ориентации, интервал распознавания графов и последовательных единиц тестирования" , Теоретическая информатика , 234 (1-2): 59-84, DOI : 10.1016 / S0304-3975 (97) 00241-7.
  • Каплан, Хаим; Шамир, Рон; Тарьян, Роберт (1999), "Решимость параметризованных задач завершения на хордовых, строго хордовых и собственных интервальных графах", SIAM J. Comput. , 28 (5): 1906–1922, DOI : 10.1137 / S0097539796303044.
  • Маффре, Фредерик (2003), «О раскраске совершенных графов», в Риде, Брюс А .; Продажи, Клаудия Л. (ред.), Последние достижения в области алгоритмов и комбинаторики , Книги CMS по математике, 11 , Springer-Verlag, стр. 65–84, DOI : 10.1007 / 0-387-22444-0_3 , ISBN 0-387-95434-1.
  • Парра, Андреас; Шеффлера, Петра (1997), "Характеризация и алгоритмические применения хорды графа вложений", Дискретная прикладная математика , 79 (1-3): 171-188, DOI : 10.1016 / S0166-218X (97) 00041-3 , МР  1478250.
  • Патил, HP (1986), «О структуре k -деревьев», Журнал комбинаторики, информации и системных наук , 11 (2–4): 57–64, MR  0966069.
  • Rose, D .; Люкер, Джордж; Тарьян, Роберт Е. (1976), "Алгоритмические аспекты устранения вершины на графах", SIAM журнал по вычислениям , 5 (2): 266-283, DOI : 10,1137 / 0205021 , МР  0408312.
  • Сеймур, PD ; Уивер, RW (1984), "Обобщение хордальных графов", Журнал теории графов , 8 (2): 241-251, DOI : 10.1002 / jgt.3190080206 , МР  0742878.
  • Szwarcfiter, JL ; Борнстейн, CF (1994), "Clique графы аккордовых и пути графов", SIAM журнал по дискретной математике , 7 (2): 331-336, DOI : 10,1137 / s0895480191223191 , ЛВП : 11422/1497.

Внешние ссылки [ править ]

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