Дистанційно-успадковуваний граф

В теорії графів дистанційно-успадковуваний граф (або цілком сепарабельний граф)[1] — це граф, у якому відстані в будь-якому зв'язному породженому підграфі такі самі, як і в початковому графі. Таким чином, будь-який породжений підграф успадковує відстані більшого графу.

Дистанційно-успадковувані графи назвав і вперше вивчив Говорка (Howorka)[2], хоча вже 1970 року Олару і Сакс (Olaru, Sachs) для еквівалентного класу графів показали, що клас містить досконалі графи[3].

Вже деякий час було відомо, що дистанційно-успадковувані графи складають клас графів перетинів[4], але модель перехрещення не була відомою, поки її не дали Іоан і Пауль (Gioan, Paul, 2012).

Визначення та опис

Оригінальне визначення дистанційно-успадковуваного графу — це граф G, такий, що, якщо будь-які дві вершини u і v належать зв'язному породженому підграфу H графу G, то деякий найкоротший шлях, що з'єднує u і v в G, має бути в підграфі H, причому відстань між u і v в H має бути такою ж, як у G.

Дистанційно-успадковувані графи можна описати кількома іншими еквівалентними способами:[5]

  • Це графи, в яких будь-який породжений шлях є найкоротшим.
  • Це графи, в яких будь-який цикл довжини щонайменше п'ять має дві або більше діагоналей і в яких будь-який цикл довжини рівно п'ять має щонайменше одну пару діагоналей, що перетинаються.
  • Це графи, в яких будь-який цикл довжини п'ять і більше має щонайменше одну пару діагоналей, що перетинаються.
  • Це графи, в яких для будь-яких чотирьох вершин u, v, w і x щонайменше дві з трьох сум відстаней d(u,v)+d(w,x), d(u,w)+d(v,x) и d(u,x)+d(v,w) рівні.
  • Це графи, в яких немає ізометричних підграфів будь-якого циклу довжини п'ять і більше або будь-якого з трьох інших графів: 5-циклу з однією хордою, 5-циклу з двома хордами, що не перетинаються і 6-циклу з хордою, що сполучає протилежні вершини.
Три операції, за допомогою яких можна побудувати будь-який дистанційно-успадковуваний граф
  • Це графи, які можна створити з однієї вершини за допомогою послідовності трьох операцій (показаних на ілюстрації):
    1. Додавання нової висячої вершини, з'єднаної одним ребром з наявною вершиною графу.
    2. Заміна будь-якої вершини графу парою вершин, кожна з яких має тих самих сусідів, що й видалена вершина. Нова пара вершин називається двійнятами.
    3. Заміна будь-якої вершини графу парою вершин, кожна з яких має тих самих сусідів, що й видалена вершина, а також іншу вершину з пари. Нова пара вершин називається близнюками.
  • Це графи, які можна повністю розкласти на кліки і зірки (повні двочасткові графи K1,q) за допомогою розщеплювальної декомпозиції . У такому розщепленні отримують розклади графу на дві підмножини, такі, що розбивні ребра, які утворюють повний двочастковий підграф, формують два менших графи заміною кожного боку двочасткового графу вершинами з рекурсивним розщепленням цих двох підграфів[6].
  • Це графи, які мають одиничну рангову ширину, де рангова ширина графу визначається як мінімум максимального рангу за всіма ієрархічними поділами вершин серед певних підматриць матриці суміжності графу, визначених поділом[7].

Зв'язок з іншими сімействами графів

Будь-який дистанційно-успадковуваний граф є досконалим[2], точніше, цілком упорядковуваним графом[8]. Будь-який дистанційно-успадковуваний граф є також парним графом, графом, у якому будь-які два шляхи між однією і тією ж парою вершин мають одночасно або парну довжину, або непарну[9]. Будь-який парний степінь дистанційно-успадковуваного графу G (тобто граф G2i, утворений з'єднанням пар вершин на відстані, що не перевищує 2i в G) є хордальним графом[10].

Будь-який дистанційно-успадковуваний граф можна подати як граф перетинів хорд у колі, тобто як коловий граф. Це можна показати, побудувавши граф за допомогою додавання висячих вершин, «двійнят» і «близнюків», формуючи при цьому на кожному кроці набір хорд, що утворює граф. Додавання висячої вершини відповідає додаванню хорди поруч з кінцем наявною хорди так, що нова хорда буде перетинати тільки цю хорду. Додавання «двійнят» відповідає заміні хорди двома паралельними хордами, що перетинають один і той самий набір хорд. Додавання «близнюків» відповідає заміні хорди двома майже паралельними перетинними хордами, які перетинають один і той самий набір інших хорд.

Дистанційно-успадковуваний граф є двочастковим тоді і тільки тоді, коли в ньому немає трикутників. Двочастковий дистанційно-успадковуваний граф можна побудувати з єдиної вершини додаванням тільки висячих вершин і «двійнят», оскільки будь-які «близнюки» утворюють трикутник, а операції додавання висячої вершини і «двійнят» зберігають двочастковість.

Графи, які можна побудувати з єдиної вершини додаванням висячих вершин і створенням «близнюків» без операції створення «двійнят», є окремими випадками птолемеєвих графів і включають блокові графи. Графи, які можна створити з єдиної вершини створенням «двійнят» і «близнюків», але без додавання висячих вершин, — це кографи, які є, таким чином, дистанційно-успадковуваними. Кографи — це точно незв'язне об'єднання дистанційно-успадковуваних графів з діаметром 2. Окіл будь-якої вершини дистанційно-успадковуваного графу є кографом. Транзитивне замикання орієнтованого графу, утвореного вибором будь-якого набору орієнтацій ребер будь-якого дерева, є дистанційно-успадковуваним. Окремий випадок, у якому дерево орієнтоване в напрямі від деякої вершини, утворює підклас дистанційно-успадковуваних графів, відомий як тривіально досконалі графи, який також називають хордальними кографами[11].

Алгоритми

Дистанційно-успадковувані графи можна розпізнати й розкласти на послідовність висячих вершин і операцій подвоєння за лінійний час[12].

Оскільки дистанційно-успадковувані графи досконалі, деякі оптимізаційні задачі можна розв'язати за поліноміальний час, хоча ці задачі NP-складні для загальніших класів графів. Отже, можна за поліноміальний час знайти максимальну кліку або незалежну множину в дистанційно-успадковуваному графі або знайти його оптимальне розфарбування[13]. Оскільки дистанційно-успадковувані графи є коловими графами, вони успадковують алгоритми з поліноміальним часом для колових графів. Наприклад, можна визначити за поліноміальний час деревну ширину будь-якого колового графу, а отже й будь-якого дистанційно-успадковуваного графу[14][15]. Крім того, клікова ширина будь-якого дистанційно-успадковуваного графу не перевищує трьох[16]. Як наслідок, за теоремою Курселя, для багатьох задач на цих графах існують ефективні алгоритми на основі динамічного програмування[17][18].

Деякі інші задачі оптимізації на дистанційно-успадковуваних графах можна розв'язати ефективно за допомогою алгоритмів, спеціально розроблених для таких графів. Як показали де Атрі та Москаріні[19], мінімальна зв'язна домінівна множина (або, еквівалентно, кістяк із максимально можливим числом листків) на дистанційно-успадковуваних графах можна знайти за поліноміальний час. Гамільтонів граф або гамільтонів шлях будь-якого дистанційно-успадковуваного графу можна знайти за поліноміальний час[20][21].

Примітки

  1. Hammer, Maffray, 1990.
  2. Howorka, 1977.
  3. Олару і Сакс показали α-досконалість графів, у яких будь-який цикл довжини п'ять і більше має пару перетинних діагоналей (Sachs, 1970, теорема 5). За Ловашем (Lovász, 1972), α-досконалість є еквівалентною формою визначення досконалих графів.
  4. McKee, McMorris, 1999.
  5. Howorka, (1977); Bandelt, Mulder, (1986); Hammer, Maffray, (1990); Brandstädt, Le, Spinrad, (1999), Теорема 10.1.1, стор. 147.
  6. Gioan, Paul, (2012). Тісно пов'язану декомпозицію використали для візуалізації графів Епштейн, Гудріх і Менг (Eppstein, Goodrich, Meng, (2006)) і (для двочасткових дистанційно-успадковуваних графів) Хуей, Шефер і Штефанкович (Hui, Schaefer, Štefankovič, (2004)).
  7. Oum, 2005.
  8. Brandstädt, Le, Spinrad, 1999, с. 70–71, 82.
  9. Brandstädt, Le, Spinrad, 1999, с. 45.
  10. Brandstädt, Le, Spinrad, 1999, с. 164 Теорема 10.6.14.
  11. Cornelsen, Di Stefano, 2005.
  12. Damiand, Habib, Paul, (2001); Gioan, Paul, (2012). До цього про границю заявили Хаммер і Маффрей (Hammer, Maffray, (1990)), але Даміанд (Damiand) виявив у міркуваннях помилку.
  13. Когіс і Тьєррі Cogis, Thierry, (2005) представили простий прямий алгоритм для пошуку максимальних зважених незалежних множин у дистанційно-успадковуваних графах, заснований на розборі графу на висячі вершини і подвійні вершини, виправивши попередню спробу створення такого алгоритму Хаммером і Маффреєм (Hammer, Maffray, (1990)). Оскільки дистанційно-успадковувані графи є цілком упорядковуваними, їх можна оптимально розфарбувати за лінійний час за допомогою алгоритму LexBFS пошуку досконалого упорядкування і застосування жадібного розфарбовування.
  14. Kloks, 1996.
  15. Brandstädt, Le, Spinrad, 1999, с. 170.
  16. Golumbic, Rotics, 2000.
  17. Courcelle, Makowski, Rotics, 2000.
  18. Espelage, Gurski, Wanke, 2001.
  19. D'Atri, Moscarini, 1988.
  20. Hsieh, Ho, Hsu, Ko, 2002.
  21. Müller, Nicolai, 1993.

Література

  • Hans-Jürgen Bandelt, Henry Martyn Mulder. Distance-hereditary graphs // Journal of Combinatorial Theory.  1986. Т. 41, вип. 2 (17 лютого). С. 182–208. — (Series B). DOI:10.1016/0095-8956(86)90043-2..
  • Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X..
  • O. Cogis, E. Thierry. Computing maximum stable sets for distance-hereditary graphs // Discrete Optimization.  2005. Т. 2, вип. 2 (17 лютого). С. 185–188. DOI:10.1016/j.disopt.2005.03.004..
  • Sabine Cornelsen, Gabriele Di Stefano. Proc. 30th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2004). — Springer-Verlag, 2005. — Т. 3353. — С. 46–57. — (Lecture Notes in Computer Science).
  • B. Courcelle, J. A. Makowski, U. Rotics. Linear time solvable optimization problems on graphs on bounded clique width // Theory of Computing Systems.  2000. Т. 33, вип. 2 (17 лютого). С. 125–150. DOI:10.1007/s002249910009..
  • Alessandro D'Atri, Marina Moscarini. Distance-hereditary graphs, Steiner trees, and connected domination // SIAM Journal on Computing.  1988. Т. 17, вип. 3 (17 лютого). С. 521–538. DOI:10.1137/0217032..
  • Guillaume Damiand, Michel Habib, Christophe Paul. A simple paradigm for graph recognition: application to cographs and distance hereditary graphs // Theoretical Computer Science.  2001. Т. 263, вип. 1–2 (17 лютого). С. 99–111. DOI:10.1016/S0304-3975(00)00234-6..
  • David Eppstein, Michael T. Goodrich, Jeremy Yu Meng. Proc. 13th Int. Symp. Graph Drawing (GD 2005) / Patrick Healy, Nikola S. Nikolov. — Springer-Verlag, 2006. — Т. 3843. — С. 165–176. — (Lecture Notes in Computer Science).
  • W. Espelage, F. Gurski, E. Wanke. Proc. 27th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2001). — Springer-Verlag, 2001. — Т. 2204. — С. 117–128. — (Lecture Notes in Computer Science).
  • Emeric Gioan, Christophe Paul. Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs // Discrete Applied Mathematics.  2012. Т. 160, вип. 6 (17 лютого). С. 708–733. arXiv:0810.1823. DOI:10.1016/j.dam.2011.05.007..
  • Martin Charles Golumbic, Udi Rotics. On the clique-width of some perfect graph classes // International Journal of Foundations of Computer Science.  2000. Т. 11, вип. 3 (17 лютого). С. 423–443. DOI:10.1142/S0129054100000260..
  • Peter Ladislaw Hammer, Frédéric Maffray. Completely separable graphs // Discrete Applied Mathematics.  1990. Т. 27, вип. 1–2 (17 лютого). С. 85–99. DOI:10.1016/0166-218X(90)90131-U..
  • Edward Howorka. A characterization of distance-hereditary graphs // The Quarterly Journal of Mathematics. Oxford. Second Series.  1977. Т. 28, вип. 112 (17 лютого). С. 417–420. DOI:10.1093/qmath/28.4.417..
  • Sun-yuan Hsieh, Chin-wen Ho, Tsan-sheng Hsu, Ming-tat Ko. Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002, Proceedings. — Springer-Verlag, 2002. — Т. 2387. — С. 51–75. — (Lecture Notes in Computer Science) — ISBN 978-3-540-43996-7. DOI:10.1007/3-540-45655-4_10..
  • Peter Hui, Marcus Schaefer, Daniel Štefankovič. Proc. 12th Int. Symp. Graph Drawing (GD 2004) / János Pach. — Springer-Verlag, 2004. — Т. 3383. — С. 318–328. — (Lecture Notes in Computer Science).
  • T. Kloks. Treewidth of circle graphs // International Journal of Foundations of Computer Science.  1996. Т. 7, вип. 2 (17 лютого). С. 111–120. DOI:10.1142/S0129054196000099..
  • László Lovász. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics.  1972. Т. 2, вип. 3 (17 лютого). С. 253–267. DOI:10.1016/0012-365X(72)90006-4..
  • Terry A. McKee, F. R. McMorris. Topics in Intersection Graph Theory. — Philadelphia : Society for Industrial and Applied Mathematics, 1999. — Т. 2. — (SIAM Monographs on Discrete Mathematics and Applications) — ISBN 0-89871-430-3.
  • Haiko Müller, Falk Nicolai. Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs // Information Processing Letters.  1993. Т. 46, вип. 5 (17 лютого). С. 225–230. DOI:10.1016/0020-0190(93)90100-N..
  • Sang-il Oum. Rank-width and vertex-minors // Journal of Combinatorial Theory.  2005. Т. 95, вип. 1 (17 лютого). С. 79–100. — (Series B). DOI:10.1016/j.jctb.2005.03.003..
  • Horst Sachs. Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969). — Gordon and Breach, 1970. — С. 377–384..

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.