WikiDer > Дистанционно-наследственный граф

Distance-hereditary graph
Дистанционно-наследственный граф.

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

Дистанционно-наследственные графы были названы и впервые изучены Ховорка (1977), хотя уже было показано, что эквивалентный класс графов идеально в 1970 году Олару и Сакс.[2]

Некоторое время было известно, что графы с дистанционной наследственностью составляют класс пересечения графов,[3] но ни одна модель пересечения не была известна, пока не была дана Джоан и Пол (2012).

Определение и характеристика

Исходное определение дистанционно-наследственного графа - это граф грамм такое, что если любые две вершины ты и v принадлежат связному индуцированному подграфу ЧАС из грамм, то некоторые кратчайший путь соединение ты и v в грамм должен быть подграфом ЧАС, так что расстояние между ты и v в ЧАС такое же, как расстояние в грамм.

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

  • Это графы, в которых каждый индуцированный путь является кратчайшим, или, что эквивалентно, графы, в которых каждый некратчайший путь имеет по крайней мере одно ребро, соединяющее две непоследовательные вершины пути.
  • Это графы, в которых каждый цикл длиной пять и более имеет как минимум две пересекающиеся диагонали.
  • Это графы, в которых для каждых четырех вершин ты, v, ш, и Икс, по крайней мере, две из трех сумм расстояний d(ты,v)+d(ш,Икс), d(ты,ш)+d(v,Икс), и d(ты,Икс)+d(v,ш) равны друг другу.
  • Это графы, которые не имеют в качестве изометрических подграфов ни одного цикла длины пять или более или любого из трех других графов: 5-цикла с одной хордой, 5-цикла с двумя непересекающимися хордами и 6-цикла с хордой, соединяющей противоположные вершины.
Три операции, с помощью которых можно построить любой дистанционно-наследственный граф.
  • Это графы, которые можно построить из одной вершины с помощью последовательности следующих трех операций, как показано на рисунке:
    1. Добавить новый кулон вершина соединены одним ребром с существующей вершиной графа.
    2. Замените любую вершину графа парой вершин, каждая из которых имеет тот же набор соседей, что и замененная вершина. Новая пара вершин называется ложные близнецы друг друга.
    3. Заменить любую вершину графа парой вершин, каждая из которых имеет в качестве своих соседей соседей замененной вершины вместе с другой вершиной пары. Новая пара вершин называется настоящие близнецы друг друга.
  • Это графы, которые можно полностью разложить на клики и звезды (полные двудольные графы K1,q) автор расщепление. В этом разложении можно найти такое разбиение графа на два подмножества, что ребра, разделяющие два подмножества, образуют полный двудольный подграф, образует два меньших графа, заменяя каждую из двух сторон разбиения одной вершиной, и рекурсивно разбивает эти два подграфа.[5]
  • Это графы с шириной ранга один, где ширина ранга графа определяется как минимальная по всем иерархическим разбиениям вершин графа максимального ранга среди определенных подматриц графа. матрица смежности определяется разделом.[6]
  • Это графики без HHDG, а это означает, что они имеют характеристика запрещенного графа согласно которому нет индуцированный подграф может быть домом ( дополнительный граф пятивершинника граф путей), отверстие (a график цикла из пяти или более вершин), домино (цикл с шестью вершинами плюс диагональное ребро между двумя противоположными вершинами) или драгоценный камень (цикл с пятью вершинами плюс две диагонали, инцидентные одной и той же вершине).

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

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

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

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

Графы, которые могут быть построены из одной вершины с помощью висячих вершин и истинных близнецов без каких-либо операций ложных двойников, являются частными случаями Птолемеевы графы и включить блочные графики. Графы, которые могут быть построены из одной вершины с помощью операций ложного двойника и истинного двойника без каких-либо висячих вершин, являются кографы, которые, следовательно, являются наследственными на расстоянии; кографы - это в точности непересекающиеся объединения дистанционно-наследственных графов диаметра 2. В район любой вершины дистанционно-наследственного графа является кографом. Транзитивное замыкание ориентированного графа, образованного выбором любого набора ориентаций для ребер любого дерево является дистанционно-наследственным; особый случай, когда дерево последовательно ориентировано от некоторой вершины, образует подкласс дистанционно-наследственных графов, известный как тривиально совершенные графы, которые также называют хордовыми кографами.[12]

Алгоритмы

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

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

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

Примечания

  1. ^ Молоток и Маффрей (1990).
  2. ^ Олару и Сакс показали α-совершенство графов, в которых каждый цикл длиной пять и более имеет пару пересекающихся диагоналей (Сакс 1970, Теорема 5). К Ловас (1972), α-совершенство - это эквивалентная форма определения совершенных графов.
  3. ^ Макки и МакМоррис (1999)
  4. ^ Ховорка (1977); Бандельт и Малдер (1986); Молоток и Маффрей (1990); Brandstädt, Le & Spinrad (1999), Теорема 10.1.1, с. 147.
  5. ^ Джоан и Пол (2012). Близкое разложение было использовано для рисунок графика к Эппштейн, Гудрич и Мэн (2006) и (для двудольных дистанционно-наследственных графов) на Хуэй, Шефер и Штефанкович (2004).
  6. ^ Оум (2005).
  7. ^ Ховорка (1977).
  8. ^ Brandstädt, Le & Spinrad (1999), стр. 70–71 и 82.
  9. ^ Brandstädt, Le & Spinrad (1999), стр.45.
  10. ^ Brandstädt, Le & Spinrad (1999), Теорема 10.6.14, с.164.
  11. ^ Двудольные дистанционно-наследственные графы, Информационная система по классам графов и их включениям, получено 30 сентября 2016 г.
  12. ^ Корнельсен и Ди Стефано (2005).
  13. ^ Дамианд, Хабиб и Пол (2001); Джоан и Пол (2012). Более ранняя линейная временная граница была заявлена Молоток и Маффрей (1990) но это было обнаружено Дамиандом как ошибочное.
  14. ^ Cogis & Thierry (2005) представить простой прямой алгоритм для максимальных взвешенных независимых множеств в дистанционно-наследственных графах, основанный на разборе графа на висячие вершины и близнецы, исправляя предыдущую попытку такого алгоритма с помощью Молоток и Маффрей (1990). Поскольку дистанционно-наследственные графы прекрасно упорядочиваются, их можно оптимально раскрасить за линейное время, используя LexBFS найти идеальный заказ, а затем применить жадная окраска алгоритм.
  15. ^ Клокс (1996); Brandstädt, Le & Spinrad (1999), п. 170.
  16. ^ Голумбик и Ротикс (2000).
  17. ^ Курсель, Маковски и Ротикс (2000); Эспелаж, Гурски и Ванке (2001).
  18. ^ Hsieh et al. (2002); Мюллер и Николай (1993).

Рекомендации

внешняя ссылка