Русская Википедия:Дистанционно-наследуемый граф

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

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

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

  • Это графы, в которых любой порождённый путь является кратчайшим.
  • Это графы, в которых любой цикл длины по меньшей мере пять имеет две или более диагоналей и в которых любой цикл длины в точности пять имеет по меньшей мере одну пару пересекающихся диагоналей.
  • Это графы, в которых любой цикл длины пять и более имеет по меньшей мере одну пару пересекающихся диагоналей.
  • Это графы, в которых для любых четырёх вершин 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-цикла с хордой, соединяющей противоположные вершины.
Файл:Distance-hereditary construction RUS.svg
Три операции, с помощью которых можно построить любой дистанционно-наследуемый граф.
  • Это графы, которые могут быть созданы из одной вершины с помощью последовательности трёх операций (показанных на иллюстрации):
    1. Добавление новой висячей вершины, соединённой одним ребром с существующей вершиной графа.
    2. Замена любой вершины графа парой вершин, каждая из которых имеет тех же соседей, что и удалённая вершина. Новая пара вершин называется двойняшками.
    3. Замена любой вершины графа парой вершин, каждая из которых имеет тех же соседей, что и удалённая вершина, включая другую вершину из пары. Новая пара вершин называется близняшками.
  • Это графы, которые могут быть полностью разложены на клики и звёзды (полные двудольные графы K1,q) с помощью Шаблон:Не переведено 5. В таком расщеплении получают разложения графа на два подмножества, такие, что разбивающие рёбра, образующие полный двудольный подграф, формируют два меньших графа путём замены каждой стороны двудольного графа на вершины с рекурсивным расщеплением этих двух подграфов[3].
  • Это графы, которые имеют единичную ранговую ширину, где ранговая ширина графа определяется как минимум максимального ранга по всем иерархическим делениям вершин среди определённых подматриц матрицы смежности графа, определённых делениемШаблон:Sfn.

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

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

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

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

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

Алгоритмы

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

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

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Олару и Сакс показали α-совершенство графов, в которых любой цикл длины пять и более имеет пару пересекающихся диагоналей (Шаблон:Harvnb, Теорема 5). Согласно Ловашу Шаблон:Harv, α-совершенство является эквивалентной формой определения совершенных графов.
  2. ↑ Шаблон:Harvtxt; Шаблон:Harvtxt; Шаблон:Harvtxt; Шаблон:Harvtxt, Теорема 10.1.1, стр. 147.
  3. ↑ Шаблон:Harvtxt. Тесно связанная декомпозиция используется для визуализации графов Эпштейном, Гудрихом и Менгом (Шаблон:Harvtxt) и (для двудольных дистанционно-наследуемых графов) Хуэем, Шефером и Штефанковичем (Шаблон:Harvtxt).
  4. ↑ Шаблон:Harvtxt; Шаблон:Harvtxt. До этого граница была заявлена Хаммером и Маффреем (Шаблон:Harvtxt), но Дамианд (Damiand) обнаружил в рассуждениях ошибку.
  5. ↑ Когис и Тьерри Шаблон:Harvtxt представили простой прямой алгоритм для поиска максимальных взвешенных независимых множеств в дистанционно-наследуемых графах, основанный на разборе графа на висячие вершины и двойные вершины, исправив предшествующую попытку создания такого алгоритма Хаммером и Маффреем (Шаблон:Harvtxt). Поскольку дистанционно-наследуемые графы являются вполне упорядочиваемыми, они могут быть оптимально раскрашены за линейное время с помощью алгоритма LexBFS поиска совершенного упорядочения и применения жадной раскраски.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Дистанционно-наследуемый_граф&oldid=9755802