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

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

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

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

В течение некоторого времени было известно, что дистанционно-наследственные графы составляют класс пересечений графов , но ни одна модель пересечения не была известна до тех пор, пока она не была предложена Джоаном и Полом (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-цикла с двумя непересекающимися хордами. с хордой, соединяющей противоположные вершины.

Три операции, с помощью которых можно построить любой дистанционно наследственный граф.

• Это графы, которые можно построить из одной вершины с помощью последовательности следующих трех операций, как показано на рисунке:
  1. Добавьте новую висячую вершину, соединенную одним ребром с существующей вершиной графа.
  2. Замените любую вершину графа парой вершин, каждая из которых имеет тот же набор соседей, что и заменяемая вершина. Новые пары вершин называются ложными двойниками друг друга.
  3. Замените любую вершину графа парой вершин, каждая из которых имеет в качестве соседей соседей заменяемой вершины вместе с другой вершиной пары. Новые пары вершин называются истинными двойниками друг друга.
• Это графы, которые можно полностью разложить на клики и звезды ( полные двудольные графы K _{1, q} ) с помощью расщепленного разложения . В этом разложении находится разделение графа на два подмножества, такое, что ребра, разделяющие два подмножества, образуют полный двудольный подграф , формируются два меньших графа путем замены каждой из двух сторон разделения на одну вершину и рекурсивно разделяет эти два подграфа.
• Это графы, которые имеют ширину ранга один, где ширина ранга графа определяется как минимальный по всем иерархическим разбиениям вершин графа максимальный ранг среди определенных подматриц матрицы смежности графа , определяемой перегородка.
• Это графы без HHDG, что означает, что они имеют запрещенную характеристику графа , согласно которой ни один индуцированный подграф не может быть домом ( графом-дополнением с пятью вершинами графа путей ), дырой ( графом циклов из пяти или более вершин). , домино (цикл из шести вершин плюс диагональное ребро между двумя противоположными вершинами) или драгоценный камень (цикл из пяти вершин плюс две диагонали, инцидентные одной и той же вершине).

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

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

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

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

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

Алгоритмы

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

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

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

Ссылки

• Бандельт, Ханс-Юрген; Малдер, Генри Мартин (1986), «Дистанционно-наследственные графы», Журнал комбинаторной теории , серия B, 41 (2): 182–208, doi : 10.1016/0095-8956(86)90043-2 , MR   0859310 .
• Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN  0-89871-432-Х .
• Когис, О.; Тьерри, Э. (2005), «Вычисление максимальных стабильных наборов для дистанционно-наследственных графов», Discrete Optimization , 2 (2): 185–188, doi : 10.1016/j.disopt.2005.03.004 , MR   2155518 .
• Корнельсен, Сабина; Ди Стефано, Габриэле (2005), «Древовидные графики сопоставимости: характеристика, распознавание и приложения», Proc. 30-й Международный Воркш. Теоретико-графовые концепции в информатике (WG 2004) , Конспекты лекций по информатике , том. 3353, Springer-Verlag, стр. 46–57, doi : 10.1007/978-3-540-30559-0_4 , MR   2158633 , S2CID   14166894 , ISBN   9783540241324 , 9783540305590 .
• Курсель, Б. ; Маковски, Дж. А.; Ротикс, У. (2000), «Задачи оптимизации, решаемые за линейное время, на графах с ограниченной шириной клики», Theory of Computing Systems , 33 (2): 125–150, doi : 10.1007/s002249910009 , S2CID   15402031 .
• Д'Атри, Алессандро; Москарини, Марина (1988), «Дистанционно-наследственные графы, деревья Штейнера и связанное доминирование», SIAM Journal on Computing , 17 (3): 521–538, doi : 10.1137/0217032 , MR   0941943 .
• Дамиан, Гийом; Хабиб, Мишель; Пол, Кристоф (2001), «Простая парадигма распознавания графов: применение к кографам и дистанционным наследственным графам» (PDF) , Theoretical Computer Science , 263 (1–2): 99–111, doi : 10.1016/S0304-3975( 00)00234-6 , МР   1846920 .
• Эппштейн, Дэвид ; Гудрич, Майкл Т .; Мэн, Джереми Ю (2006), «Дельта-сливающиеся рисунки», в Хили, Патрик; Николов Никола С. (ред.), Учеб. 13-й Международный. Симп. Рисование графиков (GD 2005) , Конспекты лекций по информатике , том. 3843, Springer-Verlag, стр. 165–176, arXiv : cs.CG/0510024 , doi : 10.1007/11618058_16 , MR   2244510 , S2CID   13478178 .
• Эспелаж, В.; Гурски, Ф.; Ванке, Э. (2001), «Как решить NP-трудные задачи с графами на графах с ограниченной шириной клика за полиномиальное время», Proc. 27-й Международный. Воркш. Теоретико-графовые концепции в информатике (WG 2001) , Конспекты лекций по информатике , том. 2204, Springer-Verlag, стр. 117–128 .
• Джоан, Эмерик; Пол, Кристоф (2012), «Разделение разложения и деревья с метками графов: характеристики и полностью динамические алгоритмы для полностью разложимых графов», Discrete Applied Mathematics , 160 (6): 708–733, arXiv : 0810.1823 , doi : 10.1016/j. dam.2011.05.007 , S2CID   6528410 .
• Голумбик, Мартин Чарльз ; Ротикс, Уди (2000), «О ширине клики некоторых классов совершенных графов», International Journal of Foundations of Computer Science , 11 (3): 423–443, doi : 10.1142/S0129054100000260 , MR   1792124 .
• Хаммер, Питер Ладислав ; Маффрэ, Фредерик (1990), «Полностью разделимые графы», Discrete Applied Mathematics , 27 (1–2): 85–99, doi : 10.1016/0166-218X(90)90131-U , MR   1055593 .
• Ховорка, Эдвард (1977), «Характеристика дистанционно-наследственных графов», Ежеквартальный журнал математики , вторая серия, 28 (112): 417–420, doi : 10.1093/qmath/28.4.417 , MR   0485544 .
• Се, Сунь-юань; Хо, Чин-вэнь; Сюй, Цань-шэн; Ко, Минг-тат (2002), «Эффективные алгоритмы для гамильтоновой задачи на дистанционно-наследственных графах», Вычисления и комбинаторика: 8-я ежегодная международная конференция, COCOON 2002, Сингапур, 15–17 августа 2002 г., Труды , конспекты лекций по информатике , том. 2387, Springer-Verlag, стр. 51–75, номер документа : 10.1007/3-540-45655-4_10 , ISBN.  978-3-540-43996-7 , МР   2064504 .
• Хуэй, Питер; Шефер, Маркус; Штефанкович, Даниэль (2004), «Железнодорожные пути и сливающиеся рисунки», в Пахе, Янош (редактор), Proc. 12-й Международный. Симп. Рисование графиков (GD 2004) , Конспекты лекций по информатике , том. 3383, Springer-Verlag, стр. 318–328 .
• Клокс, Т. (1996), «Древовидность круговых графов», Международный журнал основ компьютерных наук , 7 (2): 111–120, doi : 10.1142/S0129054196000099 .
• Ловас, Ласло (1972), «Нормальные гиперграфы и гипотеза идеального графа», Discrete Mathematics , 2 (3): 253–267, doi : 10.1016/0012-365X(72)90006-4 , MR   0302480 .
• Макки, Терри А.; МакМоррис, Ф.Р. (1999), Темы теории графов пересечений , Монографии SIAM по дискретной математике и приложениям, том. 2, Филадельфия: Общество промышленной и прикладной математики, номер документа : 10.1137/1.9780898719802 , ISBN.  0-89871-430-3 , МР   1672910
• Мюллер, Хайко; Николай, Фальк (1993), «Алгоритмы с полиномиальным временем для гамильтоновых задач на двудольных дистанционно-наследственных графах», Information Processing Letters , 46 (5): 225–230, doi : 10.1016/0020-0190(93)90100-N , MR   1228792 .
• Оум, Санг-ил (2005), «Ширина ранга и миноры вершин», Журнал комбинаторной теории , серия B, 95 (1): 79–100, doi : 10.1016/j.jctb.2005.03.003 , MR   2156341 .
• Сакс, Хорст (1970), «О гипотезе Бержа относительно совершенных графов», Комбинаторные структуры и их приложения (Proc. Calgary Internat. Conf., Калгари, Альта, 1969) , Гордон и Брич, стр. 377–384, MR   0272668 .

Внешние ссылки

• «Дистанционно-наследственные графы» , Информационная система по классам графов и их включениям .