Дистанционно-наследуемый граф

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов дистанционно-наследуемый граф (или вполне сепарабельный граф) [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) с помощью расщепляющей декомпозиции[en]. В таком расщеплении получают разложения графа на два подмножества, такие, что разбивающие рёбра, образующие полный двудольный подграф, формируют два меньших графа путём замены каждой стороны двудольного графа на вершины с рекурсивным расщеплением этих двух подграфов[6].
  • Это графы, которые имеют единичную ранговую ширину, где ранговая ширина графа определяется как минимум максимального ранга по всем иерархическим делениям вершин среди определённых подматриц матрицы смежности графа, определённых делением[7].

Связь с другими семействами графов[править | править код]

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

Любой дистанционно-наследуемый граф может быть представлен как граф пересечений хорд в окружности, то есть как круговой граф. Это можно показать путём построения графа с помощью добавления висячих вершин, «двойняшек» и «близняшек», формируя при этом на каждом шаге набор хорд представляющего графа. Добавление висячей вершины соответствует добавлению хорды рядом с концом существующей хорды так, что новая хорда будет пересекать только эту хорду. Добавление «двойняшки» соответствует замене хорды двумя параллельными хордами, пересекающими один и тот же набор хорд. Добавление «близняшки» соответствует замене хорды двумя почти параллельными пересекающимися хордами, которые пересекают один и тот же набор других хорд.

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

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

Алгоритмы[править | править код]

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

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

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

Примечания[править | править код]

  1. ↑ Hammer, Maffray, 1990.
  2. ↑ 1 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. — С. 182–208. — 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. — С. 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. — С. 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. — С. 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. — С. 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. — С. 708–733. — doi:10.1016/j.dam.2011.05.007. — arXiv:0810.1823..
  • Martin Charles Golumbic, Udi Rotics. On the clique-width of some perfect graph classes // International Journal of Foundations of Computer Science. — 2000. — Т. 11, вып. 3. — С. 423–443. — doi:10.1142/S0129054100000260..
  • Peter Ladislaw Hammer, Frédéric Maffray. Completely separable graphs // Discrete Applied Mathematics. — 1990. — Т. 27, вып. 1–2. — С. 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. — С. 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. — С. 111–120. — doi:10.1142/S0129054196000099..
  • László Lovász. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics. — 1972. — Т. 2, вып. 3. — С. 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. — С. 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. — С. 79–100. — 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..

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=Дистанционно-наследуемый_граф&oldid=136328350