В теории графов , разделе дискретной математики , дистанционно-наследственный граф (также называемый полностью сепарабельным графом ) [1] - это граф, в котором расстояния в любом связном индуцированном подграфе такие же, как и в исходном графе. Таким образом, любой индуцированный подграф наследует расстояния большего графа.
Дистанционно наследственные графы были названы и впервые изучены Ховоркой (1977) , хотя эквивалентный класс графов был уже показан как совершенный в 1970 году Олару и Саксом. [2]
Это было известно в течение некоторого времени , что расстояние наследственное графики представляют собой класс пересечения графиков , [3] , но ни одна модель пересечения не было известно до тех пор , пока один был дан Gioan и Павла (2012) .
Определение и характеристика
Первоначальное определение расстояния наследственного графа представляет собой график G таким образом, что, если любые две вершин U и V принадлежат связной индуцированный подграфу H из G , то некоторые кратчайший путь подключения U и V в G должны быть подграфом H , так что расстояние между U и V в H такое же , как расстояние в G .
Дистанционно-наследственные графы также можно охарактеризовать несколькими другими эквивалентными способами: [4]
- Это графы, в которых каждый индуцированный путь является кратчайшим, или, что эквивалентно, графы, в которых каждый некратчайший путь имеет по крайней мере одно ребро, соединяющее две непоследовательные вершины пути.
- Это графы, в которых каждый цикл длиной пять и более имеет как минимум две пересекающиеся диагонали.
- Это графы, в которых для каждых четырех вершин 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-цикл. с хордой, соединяющей противоположные вершины.
- Это графы, которые можно построить из одной вершины с помощью последовательности следующих трех операций, как показано на рисунке:
- Добавьте новую висячую вершину, соединенную одним ребром с существующей вершиной графа.
- Замените любую вершину графа парой вершин, каждая из которых имеет тот же набор соседей, что и замененная вершина. Новые пары вершин называются ложными двойниками друг друга.
- Замените любую вершину графа парой вершин, каждая из которых имеет в качестве своих соседей соседей замененной вершины вместе с другой вершиной пары. Новая пара вершин называется истинными близнецами друг друга.
- Это графы, которые можно полностью разложить на клики и звезды ( полные двудольные графы K 1, q ) с помощью расщепления . В этом разложении можно найти разделение графа на два подмножества, так что ребра, разделяющие два подмножества, образуют полный двудольный подграф , образуют два меньших графа, заменяя каждую из двух сторон разбиения одной вершиной, и рекурсивно разбивает эти два подграфа. [5]
- Это графы с шириной ранга один, где ширина ранга графа определяется как минимум по всем иерархическим разбиениям вершин графа максимального ранга среди определенных подматриц матрицы смежности графа, определяемой раздел. [6]
- Они являются HHDG свободных граф, а это означает , что они имеют запрещенный график характеристику в соответствии с которым не подграфом может быть домом ( дополнение графа из пяти вершин графа пути ), отверстие (а цикл граф из пяти или более вершин) , домино (цикл с шестью вершинами плюс диагональное ребро между двумя противоположными вершинами) или драгоценный камень (цикл с пятью вершинами плюс две диагонали, инцидентные одной и той же вершине).
Отношение к другим семействам графов
Каждое расстояние наследственного графом является идеальным графиком , [7] , более конкретно, идеально упорядочиваем график [8] и граф Meyniel . Каждый дистанционно-наследственный граф также является графом четности, графом , в котором каждые два индуцированных пути между одной и той же парой вершин имеют нечетную длину или оба имеют четную длину. [9] Каждая даже мощности на расстояние наследственного графа G (то есть граф G 2 я сформирован путем соединения пар вершин , находящиеся на расстоянии не более 2 I в G ) является хордой графа . [10]
Любой дистанционно-наследственный граф можно представить как граф пересечения хорд на окружности, образующий круговой граф . Это можно увидеть, построив граф, добавляя висячие вершины, ложные близнецы и истинные близнецы, на каждом шаге создавая соответствующий набор хорд, представляющих граф. Добавление висячей вершины соответствует добавлению хорды рядом с конечными точками существующей хорды, так что она пересекает только эту хорду; добавление ложных близнецов соответствует замене хорды двумя параллельными хордами, пересекающими тот же набор других хорд; и добавление истинных близнецов соответствует замене хорды двумя хордами, которые пересекают друг друга, но почти параллельны и пересекают тот же набор других хорд.
Дистанционно наследственный граф двудольный тогда и только тогда, когда он не содержит треугольников . Двудольные дистанционно-наследственные графы могут быть построены из одной вершины путем добавления только висячих вершин и ложных близнецов, поскольку любой истинный близнец образовал бы треугольник, но операции висячей вершины и ложные двойники сохраняют двудольность. Любой двудольный дистанционно-наследственный граф хордально двудольный и модулярный . [11]
Графы, которые могут быть построены из одной вершины с помощью висячих вершин и истинных близнецов, без каких-либо операций ложных двойников, являются частными случаями графов Птолемея и включают блочные графы . Графы, которые могут быть построены из одной вершины с помощью операций ложного близнеца и истинного близнеца без каких-либо висячих вершин, являются кографами , которые, следовательно, наследуются на расстоянии; кографы - это в точности непересекающиеся объединения дистанционно-наследственных графов диаметра 2. Окрестность любой вершины в расстоянии наследственного графа является кографом. Транзитивное замыкание ориентированного графа, образованного выбором любого набора ориентаций для ребер любого дерева, является дистанционно-наследственным; особый случай, когда дерево последовательно ориентировано от некоторой вершины, образует подкласс дистанционно-наследственных графов, известных как тривиально совершенные графы , которые также называются хордовыми кографами. [12]
Алгоритмы
Дистанционно-наследственные графы можно распознать и разобрать на последовательность операций над вершинами и близнецами за линейное время. [13]
Поскольку дистанционно-наследственные графы совершенны, некоторые задачи оптимизации могут быть решены для них за полиномиальное время, несмотря на то, что они NP-трудны для более общих классов графов. Таким образом, можно за полиномиальное время найти максимальную клику или максимальное независимое множество в дистанционно-наследственном графе или найти оптимальную раскраску любого дистанционно-наследственного графа. [14] Поскольку дистанционно-наследственные графы являются круговыми графами, они наследуют алгоритмы полиномиального времени для круговых графов; например, можно определить за полиномиальное время древовидную ширину любого кругового графа и, следовательно, любого графа с дистанционной наследственностью. [15] Кроме того, ширина клики любого дистанционно-наследственного графа не превосходит трех. [16] Как следствие, согласно теореме Курселя , эффективные алгоритмы динамического программирования существуют для многих задач на этих графах. [17]
Некоторые другие задачи оптимизации также могут быть решены более эффективно с помощью алгоритмов, специально разработанных для графов с дистанционной наследственностью. Как показывают Д'Атри и Москарини (1988) , минимальное связное доминирующее множество (или, что эквивалентно, остовное дерево с максимально возможным числом листьев) может быть найдено за полиномиальное время на дистанционно-наследственном графе. Гамильтонов цикл или гамильтонов путь любого расстояния наследственное графа также можно найти в полиномиальное время. [18]
Заметки
- ^ Молот & Maffray (1990) .
- ^ Олару и Сакс показали α-совершенство графов, в которых каждый цикл длины пять или более имеет пару пересекающихся диагоналей ( Sachs 1970 , теорема 5). Согласно Ловасу (1972) , α-совершенство является эквивалентной формой определения совершенных графов.
- ^ Макки и МакМоррис (1999)
- ^ Ховорка (1977) ; Бандельт и Малдер (1986) ; Хаммер и Маффрей (1990) ; Brandstädt, Le & Spinrad (1999) , теорема 10.1.1, с. 147.
- ^ Gioan & Paul (2012) . Близкородственное разложение использовались для графа рисунка по Eppstein, Goodrich & Мэн (2006) и (для двудольных расстояния наследственных графов) по Hui, Schaefer & Štefankovič (2004) .
- ^ Oum (2005) .
- ^ Howorka (1977) .
- ^ Brandstädt, Le & Спинрад (1999) , стр. 70-71 и 82.
- ^ Brandstädt, Le & Спинрад (1999) , с.45.
- ^ Brandstädt, Le & Спинрад (1999) , теорема 10.6.14, с.164.
- ^ Двудольные дистанционно-наследственные графы , Информационная система по классам графов и их включениям, получено 30 сентября 2016 г.
- ^ Cornelsen и Ди Стефано (2005) .
- ^ Damiand, Хабиб & Paul (2001) ; Джоан и Пол (2012) . Более ранняя линейная временная граница была заявлена Хаммером и Маффрей (1990), но Дамианд обнаружил, что она ошибочна.
- ^ Cogis & Thierry (2005) представляют простой прямой алгоритм для максимально взвешенных независимых множеств в дистанционно-наследственных графах, основанный на разборе графа на висячие вершины и близнецы, исправляя предыдущую попытку такого алгоритма Hammer & Maffray (1990) . Поскольку дистанционно-наследственные графы идеально упорядочиваются, их можно оптимально раскрасить за линейное время, используя LexBFS для нахождения идеального порядка и затем применяяалгоритм жадной раскраски .
- ^ Клокс (1996) ; Brandstädt, Le & Spinrad (1999) , стр. 170.
- ^ Golumbic & Rotics (2000) .
- ^ Курсель, Маковски и Ротикс (2000) ; Эспелаж, Гурски и Ванке (2001) .
- ^ Hsieh et al. (2002) ; Мюллер и Николай (1993) .
Рекомендации
- Бандельт, Ханс-Юрген; Малдер, Генри Мартин (1986), "Дистанционно-наследственная графы", Журнал комбинаторной теории , серии B, 41 (2): 182-208, DOI : 10,1016 / 0095-8956 (86) 90043-2 , MR 0859310.
- Брандштадт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
- Cogis, O .; Тьерри, Е. (2005), "Вычисление максимальных наборов стабильных для расстояния наследственных графов", дискретная оптимизация , 2 (2): 185-188, DOI : 10.1016 / j.disopt.2005.03.004 , МР 2155518.
- Корнельсен, Сабина; Ди Стефано, Габриэле (2005), «Древовидные графы сопоставимости: характеризация, распознавание и приложения», Proc. 30-й Int. Worksh. График Теоретико-концепции в области компьютерных наук (РГ 2004) , Lecture Notes в области компьютерных наук , 3353 , Springer-Verlag, стр 46-57,. Дои : 10.1007 / 978-3-540-30559-0_4 , MR 2158633 , S2CID 14166894, ISBN 9783540241324 , 9783540305590 .
- Курсель, Б .; Маковски, JA; Rotics, У. (2000), "Линейные временные проблемы разрешимы оптимизации на графиках на ограниченной ширины кликовым", Теория вычислительных систем , 33 (2): 125-150, DOI : 10.1007 / s002249910009.
- Д'Атри, Алессандро; Moscarini, Марина (1988), "Расстояние-наследственные графы, деревья, Steiner и связное доминирование", SIAM журнал по вычислениям , 17 (3): 521-538, DOI : 10,1137 / 0217032 , МР 0941943.
- Дамианд, Гийом; Хабиб, Мишель; Пол, Кристоф (2001), «Простая парадигма для распознавания графов: приложение к кографам и дистанционным наследственным графам» (PDF) , Теоретическая информатика , 263 (1–2): 99–111, DOI : 10.1016 / S0304-3975 ( 00) 00234-6 , MR 1846920.
- Эпштейн, Дэвид ; Гудрич, Майкл Т .; Менг, Джереми Ю (2006), «Дельта-сливающиеся рисунки», в Хили, Патрик; Николов, Никола С. (ред.), Proc. 13-е межд. Symp. Graph Drawing (GD 2005) , Lecture Notes in Computer Science , 3843 , Springer-Verlag, pp. 165–176, arXiv : cs.CG/0510024 , doi : 10.1007 / 11618058_16 , MR 2244510.
- Espelage, W .; Гурски, Ф .; Ванке, Э. (2001), "Как решить NP-трудные задачи о графах на ограниченных графах шириной клики за полиномиальное время", Proc. 27-й Int. Worksh. Теоретико-графические концепции в компьютерных науках (WG 2001) , Lecture Notes in Computer Science , 2204 , Springer-Verlag, pp. 117–128.
- Джоан, Эмерик; Пол, Кристоф (2012), «Расщепляемая декомпозиция и деревья, помеченные графами: характеризации и полностью динамические алгоритмы для полностью разложимых графов», Дискретная прикладная математика , 160 (6): 708–733, arXiv : 0810.1823 , doi : 10.1016 / j. плотина.2011.05.007.
- Голумбик, Мартин Чарльз ; Rotics, удинские (2000), "О кликовым ширины некоторых совершенных классов графов", Международный журнал Основы информатики , 11 (3): 423-443, DOI : 10.1142 / S0129054100000260 , MR 1792124 CS1 maint: обескураженный параметр ( ссылка ).
- Хаммер, Питер Лэдислав ; Маффре, Фредерик (1990), «Полностью разделимые графы», Дискретная прикладная математика , 27 (1-2): 85–99, DOI : 10.1016 / 0166-218X (90) 90131-U , MR 1055593 CS1 maint: обескураженный параметр ( ссылка ).
- Howorka, Эдвард (1977), "Характеристика расстояния наследственных графов", Ежеквартальный журнал математика , Вторая серия, 28 (112): 417-420, DOI : 10,1093 / qmath / 28.4.417 , МР 0485544.
- Се, Сунь-юань; Хо, Чин-вэнь; Сюй, Цань-шэн; Ко, Минг-тат (2002), "Эффективные алгоритмы для гамильтоновой проблемы на графах с дистанционным наследием", Вычисления и комбинаторика: 8-я ежегодная международная конференция, COCOON 2002, Сингапур, 15–17 августа 2002 г., Труды , Лекционные заметки по компьютерным наукам , 2387 , Springer-Verlag, стр. 51–75, DOI : 10.1007 / 3-540-45655-4_10 , ISBN 978-3-540-43996-7, Руководство MR 2064504.
- Хуэй, Питер; Шефер, Маркус; Штефанкович, Даниэль (2004), «Железнодорожные пути и сходящиеся рисунки», в Pach, János (ed.), Proc. 12-е межд. Symp. Graph Drawing (GD 2004) , Lecture Notes in Computer Science , 3383 , Springer-Verlag, стр. 318–328..
- Kloks, Т. (1996), "древесная ширина из круга графов", Международный журнал Основы информатики , 7 (2): 111-120, DOI : 10,1142 / S0129054196000099.
- Ловас, Ласло (1972), «Нормальные гиперграфы и гипотеза идеального графа», Дискретная математика , 2 (3): 253–267, DOI : 10.1016 / 0012-365X (72) 90006-4 , MR 0302480 CS1 maint: обескураженный параметр ( ссылка ).
- Макки, Терри А .; МсМогпз, FR (1999), темы в Пересечения теории графов , SIAM Монографии по дискретной математике и ее приложениям, 2 , Филадельфия: Общество промышленной и прикладной математики, DOI : 10,1137 / +1,9780898719802 , ISBN 0-89871-430-3, Руководство по ремонту 1672910
- Мюллер, Хайко; Николай, Фальк (1993), "Алгоритмы с полиномиальным временем для гамильтоновых задач на двудольных дистанционно-наследственных графах", Письма об обработке информации , 46 (5): 225–230, DOI : 10.1016 / 0020-0190 (93) 90100-N , MR 1228792.
- Оум, Sang-ил (2005), "Ранг ширины и вершинных-миноры", Журнал комбинаторной теории , Series B, 95 (1): 79-100, DOI : 10.1016 / j.jctb.2005.03.003 , МР 2156341.
- Сакс, Хорст (1970), «О гипотезе Берже относительно совершенных графов», Комбинаторные структуры и их приложения (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) , Gordon and Breach, pp. 377–384, MR. 0272668.
Внешние ссылки
- «Дистанционно-наследственные графы» , Информационная система по классам графов и их включениям..