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

В теории графов дистанционно-наследуемый граф (или вполне сепарабельный граф) [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. С. 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..

Ссылки

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