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

elizabeth
  • 2021-04-04
  • 2

В теории графов дистанционно-наследуемый граф (или вполне сепарабельный граф ) — это граф, в котором расстояния в любом связном порождённом подграфе те же самые, что и в исходном графе. Таким образом, любой порождённый подграф наследует расстояния большего графа.

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

Уже некоторое время было известно, что дистанционно-наследуемые графы составляют класс графов пересечений , но модель пересечения не была известна, пока её не дали Иоан и Пауль ( ).

Определение и описание

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

Дистанционно-наследуемые графы могут быть описаны несколькими другими эквивалентными способами:

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

Связь с другими семействами графов

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

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

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

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

Алгоритмы

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

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

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

Примечания

  1. .
  2. ↑ .
  3. Олару и Сакс показали α-совершенство графов, в которых любой цикл длины пять и более имеет пару пересекающихся диагоналей ( , Теорема 5). Согласно Ловашу ( ), α-совершенство является эквивалентной формой определения совершенных графов.
  4. .
  5. ; ; ; , Теорема 10.1.1, стр. 147.
  6. . Тесно связанная декомпозиция используется для визуализации графов Эпштейном, Гудрихом и Менгом ( ) и (для двудольных дистанционно-наследуемых графов) Хуэем, Шефером и Штефанковичем ( ).
  7. .
  8. , с. 70–71, 82.
  9. , с. 45.
  10. , с. 164 Теорема 10.6.14.
  11. .
  12. ; . До этого граница была заявлена Хаммером и Маффреем ( ), но Дамианд (Damiand) обнаружил в рассуждениях ошибку.
  13. Когис и Тьерри представили простой прямой алгоритм для поиска максимальных взвешенных независимых множеств в дистанционно-наследуемых графах, основанный на разборе графа на висячие вершины и двойные вершины, исправив предшествующую попытку создания такого алгоритма Хаммером и Маффреем ( ). Поскольку дистанционно-наследуемые графы являются вполне упорядочиваемыми, они могут быть оптимально раскрашены за линейное время с помощью алгоритма LexBFS поиска совершенного упорядочения и применения жадной раскраски .
  14. .
  15. , с. 170.
  16. .
  17. .
  18. .
  19. .
  20. .
  21. .

Литература

  • Hans-Jürgen Bandelt, Henry Martyn Mulder. Distance-hereditary graphs // Journal of Combinatorial Theory . — 1986. — Т. 41 , вып. 2 . — С. 182–208 . — 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 . — С. 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. — ( ). .
  • 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 : . .
  • Alessandro D'Atri, Marina Moscarini. Distance-hereditary graphs, Steiner trees, and connected domination // . — 1988. — Т. 17 , вып. 3 . — С. 521–538 . — doi : . .
  • Guillaume Damiand, Michel Habib, Christophe Paul. A simple paradigm for graph recognition: application to cographs and distance hereditary graphs // . — 2001. — Т. 263 , вып. 1–2 . — С. 99–111 . — doi : . .
  • David Eppstein, Michael T. Goodrich, Jeremy Yu Meng. / Patrick Healy, Nikola S. Nikolov. — Springer-Verlag, 2006. — Т. 3843. — С. 165–176. — ( ). .
  • W. Espelage, F. Gurski, E. Wanke. Proc. 27th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2001). — Springer-Verlag, 2001. — Т. 2204. — С. 117–128. — ( ). .
  • Emeric Gioan, Christophe Paul. // . — 2012. — Т. 160 , вып. 6 . — С. 708–733 . — doi : . — arXiv : . .
  • 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 : . .
  • Peter Ladislaw Hammer, Frédéric Maffray. Completely separable graphs // . — 1990. — Т. 27 , вып. 1–2 . — С. 85–99 . — doi : . .
  • Edward Howorka. A characterization of distance-hereditary graphs // The Quarterly Journal of Mathematics. Oxford. Second Series. — 1977. — Т. 28 , вып. 112 . — С. 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. — ( ). — ISBN 978-3-540-43996-7 . — doi : . .
  • Peter Hui, Marcus Schaefer, Daniel Štefankovič. / János Pach. — Springer-Verlag, 2004. — Т. 3383. — С. 318–328. — ( ). .
  • T. Kloks. Treewidth of circle graphs // International Journal of Foundations of Computer Science. — 1996. — Т. 7 , вып. 2 . — С. 111–120 . — doi : . .
  • László Lovász. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics . — 1972. — Т. 2 , вып. 3 . — С. 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 // . — 1993. — Т. 46 , вып. 5 . — С. 225–230 . — doi : . .
  • Sang-il Oum. Rank-width and vertex-minors // Journal of Combinatorial Theory . — 2005. — Т. 95 , вып. 1 . — С. 79–100 . — doi : . .
  • Horst Sachs. Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969). — Gordon and Breach, 1970. — С. 377–384. .

Ссылки

  • , {{ citation }} : В |contribution-url= пропущен заголовок ( справка ) ; Неизвестный параметр |вклад= игнорируется ( справка ) .
Источник —

elizabeth
  • 2021-04-04
  • 2
  • Tags:

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

The title for the last searches