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

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

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

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

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

Оригинальное определение дистанционно-наследуемого графа — это граф 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-цикла с хордой, соединяющей противоположные вершины.

Это графы, которые могут быть созданы из одной вершины с помощью последовательности трёх операций (показанных на иллюстрации):
Добавление новой висячей вершины, соединённой одним ребром с существующей вершиной графа.
Замена любой вершины графа парой вершин, каждая из которых имеет тех же соседей, что и удалённая вершина. Новая пара вершин называется двойняшками.
Замена любой вершины графа парой вершин, каждая из которых имеет тех же соседей, что и удалённая вершина, включая другую вершину из пары. Новая пара вершин называется близняшками.
Это графы, которые могут быть полностью разложены на клики и звёзды (полные двудольные графы K1,q) с помощью расщепляющей декомпозиции. В таком расщеплении получают разложения графа на два подмножества, такие, что разбивающие рёбра, образующие полный двудольный подграф, формируют два меньших графа путём замены каждой стороны двудольного графа на вершины с рекурсивным расщеплением этих двух подграфов.
Это графы, которые имеют единичную ранговую ширину, где ранговая ширина графа определяется как минимум максимального ранга по всем иерархическим делениям вершин среди определённых подматриц матрицы смежности графа, определённых делением.

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

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

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

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

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

Алгоритмы

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

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

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