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

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

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

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

Хордальні графи є підмножиною досконалих графів. Їх також іноді називають циклічно жорсткими графами[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].

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. ↑ а б G. A. Dirac. On rigid circuit graphs // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1961. — Т. 25 (21 квітня). — С. 71–76. — DOI:10.1007/BF02992776..
  2. ↑ D. R. Fulkerson, O. A. Gross. Incidence matrices and interval graphs // Pacific J. Math. — 1965. — Т. 15 (21 квітня). — С. 835–855..
  3. ↑ D. Rose, George Lueker, Robert E. Tarjan. Algorithmic aspects of vertex elimination on graphs // SIAM Journal on Computing. — 1976. — Т. 5, вип. 2 (21 квітня). — С. 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 (21 квітня). — С. 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. — 21 квітня..
  6. ↑ Anne Berry, Martin Charles Golumbic, Marina Lipshteyn. Recognizing chordal probe graphs and cycle-bicolorable graphs // SIAM Journal on Discrete Mathematics. — 2007. — Т. 21, вип. 3 (21 квітня). — С. 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 (21 квітня). — С. 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: (PDF).
  10. ↑ Fănică Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs // Издание of Combinatorial Theory, Series B. — 1974. — Т. 16 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 57–64..
  13. ↑ P. D. Seymour, R. W. Weaver. A generalization of chordal graphs // Издание of Graph Theory. — 1984. — Т. 8, вип. 2 (21 квітня). — С. 241–251. — DOI:10.1002/jgt.3190080206.

Література[ред. | ред. код]

  • Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980..

Посилання[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Хордальний_граф&oldid=39470922