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

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

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

Еквівалентне визначення — якщо будь-який цикл без хорд має не більше трьох ребер. Іншими словами, хордальний граф — це граф без породжених циклів довжини більше ніж три.

Хордальні графи є підмножиною досконалих графів. Їх також іноді називають циклічно жорсткими графами[1] або тріангульованими графами. (Останній термін іноді помилково використовують для планарної тріангуляції. Див. максимальні планарні графи.)

Досконале виключення і ефективне розпізнавання хордальних графів

Досконалий порядок виключення в графі — це порядок вершин графу, такий, що для кожної вершини v, v і сусіди v, що розташовані після v в упорядкуванні, утворюють кліку. Граф хордальний тоді й лише тоді, коли має досконалий порядок виключення[2].

Роуз, Люкер і Тар'ян (1976)[3] (див. також Хабіб, Макконнел, Пауль, В'єнно (2000)[4]) показали, що досконалий порядок виключення хордального графу можна ефективно знайти за допомогою алгоритму, відомого як лексикографічний пошук у ширину. Цей алгоритм поділяє вершини графу у послідовність множин. Спочатку послідовність складається з єдиного набору, який містить усі вершини. Алгоритм у циклі вибирає вершину v з найстарішої множини в послідовності, яка містить ще не вибрані вершини, і ділить кожну множину S послідовності на дві менших — одна складається з сусідів вершини v в S, в іншу потрапляють решта вершин. Коли процес поділу проведено для всіх вершин, всі множини послідовності містять по одній вершині і утворюють послідовність, обернену досконалому порядку виключення.

Оскільки обидва процеси — і лексикографічний пошук у ширину, і перевірку, чи є порядок ідеальним виключенням, можна здійснити за лінійний час, можливо розпізнати хордальний граф за лінійний час. Задача про сендвіч на хордальному графі є 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-дерев, а тому вони також хордальні.

Суперкласи

Хордальні графи є підкласом добре відомих досконалих графів. Іншими суперкласи хордальних графів є слабкі хордальні графи, графи без непарних дірок, і графи без парних дірок. Фактично хордальні графи — це точно графи, одночасно без парних дір і без непарних дір (див. діра в теорії графів).

Будь-який хордальний граф є стиснутим, тобто графом, у якого будь-який периферійний цикл є трикутником, оскільки периферійні цикли є окремим випадком породженого циклу. Стиснуті графи можна утворити сумами за кліками хордальних графів і максимальних хордальних графів. Таким чином, стиснуті графи включають максимальні планарні графи[13].

Примітки
  1. G. A. Dirac. On rigid circuit graphs // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1961. — Т. 25 (23 січня). — С. 71–76. — DOI:10.1007/BF02992776..
  2. D. R. Fulkerson, O. A. Gross. Incidence matrices and interval graphs // Pacific J. Math. — 1965. — Т. 15 (23 січня). — С. 835–855..
  3. D. Rose, George Lueker, Robert E. Tarjan. Algorithmic aspects of vertex elimination on graphs // SIAM Journal on Computing. — 1976. — Т. 5, вип. 2 (23 січня). — С. 266–283. — DOI:10.1137/0205021..
  4. 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 (23 січня). — С. 59–84. — DOI:10.1016/S0304-3975(97)00241-7..
  5. 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. — 23 січня..
  6. Anne Berry, Martin Charles Golumbic, Marina Lipshteyn. Recognizing chordal probe graphs and cycle-bicolorable graphs // SIAM Journal on Discrete Mathematics. — 2007. — Т. 21, вип. 3 (23 січня). — С. 573–591. — DOI:10.1137/050637091..
  7. 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 (23 січня). — С. 303–317. — DOI:10.1016/S0304-3975(03)00221-4..
  8. 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..
  9. Peter Bartlett. Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations:.
  10. Fănică Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs // Издание of Combinatorial Theory, Series B. — 1974. — Т. 16 (23 січня). — С. 47–56. — DOI:10.1016/0095-8956(74)90094-X..
  11. E. A. Bender, L. B. Richmond, N. C. Wormald. Almost all chordal graphs split // J. Austral. Math. Soc.. — 1985. — Т. 38, вип. 2 (23 січня). — С. 214–221. — (A). — DOI:10.1017/S1446788700023077..
  12. H. P. Patil. On the structure of k-trees // Издание of Combinatorics, Information and System Sciences. — 1986. — Т. 11, вип. 2–4 (23 січня). — С. 57–64..
  13. P. D. Seymour, R. W. Weaver. A generalization of chordal graphs // Издание of Graph Theory. — 1984. — Т. 8, вип. 2 (23 січня). — С. 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.