Дистанційно-успадковуваний граф
В теорії графів дистанційно-успадковуваний граф (або цілком сепарабельний граф)[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-циклу з хордою, що сполучає протилежні вершини.
- Це графи, які можна створити з однієї вершини за допомогою послідовності трьох операцій (показаних на ілюстрації):
- Додавання нової висячої вершини, з'єднаної одним ребром з наявною вершиною графу.
- Заміна будь-якої вершини графу парою вершин, кожна з яких має тих самих сусідів, що й видалена вершина. Нова пара вершин називається двійнятами.
- Заміна будь-якої вершини графу парою вершин, кожна з яких має тих самих сусідів, що й видалена вершина, а також іншу вершину з пари. Нова пара вершин називається близнюками.
- Це графи, які можна повністю розкласти на кліки і зірки (повні двочасткові графи 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].
Примітки
- Hammer, Maffray, 1990.
- Howorka, 1977.
- Олару і Сакс показали α-досконалість графів, у яких будь-який цикл довжини п'ять і більше має пару перетинних діагоналей (Sachs, 1970, теорема 5). За Ловашем (Lovász, 1972), α-досконалість є еквівалентною формою визначення досконалих графів.
- McKee, McMorris, 1999.
- Howorka, (1977); Bandelt, Mulder, (1986); Hammer, Maffray, (1990); Brandstädt, Le, Spinrad, (1999), Теорема 10.1.1, стор. 147.
- Gioan, Paul, (2012). Тісно пов'язану декомпозицію використали для візуалізації графів Епштейн, Гудріх і Менг (Eppstein, Goodrich, Meng, (2006)) і (для двочасткових дистанційно-успадковуваних графів) Хуей, Шефер і Штефанкович (Hui, Schaefer, Štefankovič, (2004)).
- Oum, 2005.
- Brandstädt, Le, Spinrad, 1999, с. 70–71, 82.
- Brandstädt, Le, Spinrad, 1999, с. 45.
- Brandstädt, Le, Spinrad, 1999, с. 164 Теорема 10.6.14.
- Cornelsen, Di Stefano, 2005.
- Damiand, Habib, Paul, (2001); Gioan, Paul, (2012). До цього про границю заявили Хаммер і Маффрей (Hammer, Maffray, (1990)), але Даміанд (Damiand) виявив у міркуваннях помилку.
- Когіс і Тьєррі Cogis, Thierry, (2005) представили простий прямий алгоритм для пошуку максимальних зважених незалежних множин у дистанційно-успадковуваних графах, заснований на розборі графу на висячі вершини і подвійні вершини, виправивши попередню спробу створення такого алгоритму Хаммером і Маффреєм (Hammer, Maffray, (1990)). Оскільки дистанційно-успадковувані графи є цілком упорядковуваними, їх можна оптимально розфарбувати за лінійний час за допомогою алгоритму LexBFS пошуку досконалого упорядкування і застосування жадібного розфарбовування.
- Kloks, 1996.
- Brandstädt, Le, Spinrad, 1999, с. 170.
- Golumbic, Rotics, 2000.
- Courcelle, Makowski, Rotics, 2000.
- Espelage, Gurski, Wanke, 2001.
- D'Atri, Moscarini, 1988.
- Hsieh, Ho, Hsu, Ko, 2002.
- 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: ..
- 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: ..
- 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: ..
- Alessandro D'Atri, Marina Moscarini. Distance-hereditary graphs, Steiner trees, and connected domination // SIAM Journal on Computing. — 1988. — Т. 17, вип. 3 (17 лютого). — С. 521–538. — DOI: ..
- 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: ..
- 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: ..
- 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: ..
- Peter Ladislaw Hammer, Frédéric Maffray. Completely separable graphs // Discrete Applied Mathematics. — 1990. — Т. 27, вип. 1–2 (17 лютого). — С. 85–99. — DOI: ..
- Edward Howorka. A characterization of distance-hereditary graphs // The Quarterly Journal of Mathematics. Oxford. Second Series. — 1977. — Т. 28, вип. 112 (17 лютого). — С. 417–420. — DOI: ..
- 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:.
- 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: ..
- László Lovász. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics. — 1972. — Т. 2, вип. 3 (17 лютого). — С. 253–267. — DOI: ..
- 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: ..
- Sang-il Oum. Rank-width and vertex-minors // Journal of Combinatorial Theory. — 2005. — Т. 95, вип. 1 (17 лютого). — С. 79–100. — (Series B). — DOI: ..
- Horst Sachs. Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969). — Gordon and Breach, 1970. — С. 377–384..