Хордальний граф
В теорії графів граф називається хордальним, якщо кожен з його циклів, що мають чотири ребра і більше, має хорду (ребро, що з'єднує дві вершини циклу, але не є його частиною).
Еквівалентне визначення — якщо будь-який цикл без хорд має не більше трьох ребер. Іншими словами, хордальний граф — це граф без породжених циклів довжини більше ніж три.
Хордальні графи є підмножиною досконалих графів. Їх також іноді називають циклічно жорсткими графами[1] або тріангульованими графами. (Останній термін іноді помилково використовують для планарної тріангуляції. Див. максимальні планарні графи.)
Досконалий порядок виключення в графі — це порядок вершин графа, такий, що для кожної вершини v, v і сусіди v, що розташовані після v в упорядкуванні, утворюють кліку. Граф хордальний тоді й лише тоді, коли має досконалий порядок виключення[2].
Роуз, Люкер і Тар'ян (1976)[3] (див. також Хабіб, Макконнел, Пауль, В'єнно (2000)[4]) показали, що досконалий порядок виключення хордального графа можна ефективно знайти за допомогою алгоритму, відомого як лексикографічний пошук у ширину. Цей алгоритм поділяє вершини графа у послідовність множин. Спочатку послідовність складається з єдиного набору, який містить усі вершини. Алгоритм у циклі вибирає вершину v з найстарішої множини в послідовності, яка містить ще не вибрані вершини, і ділить кожну множину S послідовності на дві менших — одна складається з сусідів вершини v в S, в іншу потрапляють решта вершин. Коли процес поділу проведено для всіх вершин, всі множини послідовності містять по одній вершині і утворюють послідовність, обернену досконалому порядку виключення.
Оскільки обидва процеси — і лексикографічний пошук у ширину, і перевірку, чи є порядок ідеальним виключенням, можна здійснити за лінійний час, можливо розпізнати хордальний граф за лінійний час. Задача про сендвіч[en] на хордальному графі є NP-повною[5], тоді як задача про тестовий граф на хордальному графі має поліноміальну за часом складність[6].
Множину всіх досконалих порядків виключення хордального графа можна розглядати як базові слова антиматроїда. Чандран і співавтори[7] використовували цей зв'язок з антиматроїдами як частину алгоритму для ефективного перерахування всіх досконалих порядків виключення для заданого хордального графа.
Ще одне застосування досконалого порядку виключення — це пошук максимальної кліки хордального графа за поліноміальний час, тоді як для графів загального вигляду ця задача є NP-повною (хордальный граф може мати лише лінійно багато найбільших клік, тоді як нехордальні графи можуть мати їх експоненціально багато). Для того, щоб отримати список усіх найбільших клік хордального графа, достатньо знайти досконалий порядок виключення, побудувати кліку для кожної вершини v з усіх сусідніх вершин, що йдуть у порядку після v, і перевірити, чи є отримана кліка найбільшою.
Найбільша кліка, яка має максимальний розмір, — це максимальна кліка і, оскільки хордальні графи досконалі, розмір цієї кліки дорівнює хроматичному числу хордального графа. Хордальні графи є цілком упорядковуваними — оптимальну розмальовку можна отримати за допомогою алгоритму жадібної розмальовки, взявши вершини у зворотному до досконалого виключення порядку.[8]
В будь-якому графі вершинний сепаратор — це набір вершин, видалення якого робить залишок графа незв'язним. Сепаратор мінімальний, якщо він не містить підмножини, яка теж є сепаратором. Відповідно до теореми Дірака[1], хордальні графи — це графи, в яких кожен мінімальний сепаратор є клікою. Дірак використовував цю характеристику для доведення того, що хордальні графи є досконалими.
Сімейство хордальних графів можна визначити як множину графів, вершини яких можна розділити на три порожні підмножини A, Sі B, таких, що A ∪ S і S ∪ B обидва утворюють хордальні породжені підграфи, S є клікою, і немає ребер, що зв'язують A і B. Таким чином, це графи, які допускають рекурсивне розбиття на менші підграфи за допомогою клік. З цієї причини хордальні графи іноді називають розкладаними графами.[9]
Інша характеристика хордальних графів[10] використовує дерева та їх піддерева.
З набору піддерев дерева можна визначити граф піддерев — граф перетинів, кожна вершина якого відповідає піддереву і ребро з'єднує два піддерева, якщо вони мають одне або більше спільних ребер. Гаврил показав, що графи піддерев — це точно хордальні графи.
Подання хордальних графів як графів перетинів піддерев утворює розкладення графа на дерева з деревною шириною на одиницю меншою від розміру найбільшої кліки графа. Розкладення будь-якого графа G на дерева можна розглядати як подання графа G як підграфа хордального графа. Розкладення графа на дерева є також деревом об'єднання в алгоритмі поширення переконання.
Інтервальні графи — це графи перетинів піддерев шляхів, окремого випадку дерев. Таким чином, інтервальні графи є підсімейством хордальних графів.
Розщеплювані графи одночасно й самі хордальні, і є доповненнями хордальних графів. Бендер, Річмонд і Вормальд (1985)[11] показали, що при прямуванні n до нескінченності частка хордальних графів з n вершинами, які є розщеплюваними, прямує до одиниці.
Графи Птолемея — це графи, одночасно хордальні і дистанційно-успадковувані. Квазіпорогові графи є підкласом графів Птолемея, що є одночасно хордальними і кографами. Блокові графи — інший підклас графів Птолемея, в яких дві будь-які найбільші кліки мають максимум одну спільну вершину. Особливим випадком є вітряки, в яких спільна вершина одна для будь-якої пари клік.
Строго хордальні графи — це графи, що є хордальними і не містять n-сонця (n≥3) як породженого підграфа.
K-дерева — це хордальні графи, в яких всі найбільші кліки і максимальні сепаратори клік мають однаковий розмір.[12] Мережі Аполлонія — це хордальні максимальні планарні графи, або, що еквівалентно, планарні 3-дерева. Максимальні зовніпланарні графи — це підклас 2-дерев, а тому вони також хордальні.
Хордальні графи є підкласом добре відомих досконалих графів. Іншими суперкласи хордальних графів є слабкі хордальні графи, графи без непарних дірок, і графи без парних дірок[en]. Фактично хордальні графи — це точно графи, одночасно без парних дір і без непарних дір (див. діра в теорії графів).
Будь-який хордальний граф є стиснутим, тобто графом, у якого будь-який периферійний цикл є трикутником, оскільки периферійні цикли є окремим випадком породженого циклу. Стиснуті графи можна утворити сумами за кліками хордальних графів і максимальних хордальних графів. Таким чином, стиснуті графи включають максимальні планарні графи[13].
- ↑ а б G. A. Dirac. On rigid circuit graphs // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1961. — Т. 25 (6 листопада). — С. 71–76. — DOI:..
- ↑ D. R. Fulkerson, O. A. Gross. Incidence matrices and interval graphs // Pacific J. Math. — 1965. — Т. 15 (6 листопада). — С. 835–855..
- ↑ D. Rose, George Lueker, Robert E. Tarjan. Algorithmic aspects of vertex elimination on graphs // SIAM Journal on Computing. — 1976. — Т. 5, вип. 2 (6 листопада). — С. 266–283. — DOI:..
- ↑ 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 (6 листопада). — С. 59–84. — DOI:..
- ↑ 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. — 6 листопада..
- ↑ Anne Berry, Martin Charles Golumbic, Marina Lipshteyn. Recognizing chordal probe graphs and cycle-bicolorable graphs // SIAM Journal on Discrete Mathematics. — 2007. — Т. 21, вип. 3 (6 листопада). — С. 573–591. — DOI:..
- ↑ 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 (6 листопада). — С. 303–317. — DOI:..
- ↑ 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:.
- ↑ Peter Bartlett. Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations: (PDF).
- ↑ Fănică Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs // Издание of Combinatorial Theory, Series B. — 1974. — Т. 16 (6 листопада). — С. 47–56. — DOI:..
- ↑ E. A. Bender, L. B. Richmond, N. C. Wormald. Almost all chordal graphs split // J. Austral. Math. Soc.. — 1985. — Т. 38, вип. 2 (6 листопада). — С. 214–221. — (A). — DOI:..
- ↑ H. P. Patil. On the structure of k-trees // Издание of Combinatorics, Information and System Sciences. — 1986. — Т. 11, вип. 2–4 (6 листопада). — С. 57–64..
- ↑ P. D. Seymour, R. W. Weaver. A generalization of chordal graphs // Издание of Graph Theory. — 1984. — Т. 8, вип. 2 (6 листопада). — С. 241–251. — DOI:.
- Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980..
- Information System on Graph Class Inclusions: chordal graph
- Weisstein, Eric W. Хордальний граф(англ.) на сайті Wolfram MathWorld.