Сильно хордальный граф
В математической области теории графов неориентированный граф G является сильно хордальным , если это хордальный граф и каждый цикл четной длины (≥ 6) в G имеет нечетную хорду , то есть ребро, соединяющее две вершины , которые являются нечетными. расстояние (>1) друг от друга в цикле. [1]
Характеристики
[ редактировать ]Сильно хордальные графы имеют запрещенную характеристику подграфа как графы, которые не содержат индуцированного цикла длины больше трех или n -солнца ( n ≥ 3) в качестве индуцированного подграфа . [2] n U -солнце — это хордальный граф с 2 n вершинами, разделенный на два подмножества вершина = { u 1 , u 2 ,...} и W = { w 1 , w 2 ,...}, такие, что каждая w i в W имеет ровно двух соседей, u i и u ( i + 1) mod n . n u быть сильно хордальным, так как цикл 1 w w 1 u 2 2 -солнце не может ... не имеет нечетной хорды.
Сильно хордальные графы также можно охарактеризовать как графы, имеющие строгий совершенный порядок исключения, то есть такой порядок вершин, что соседи любой вершины, которые идут позже в порядке, образуют клику и такой, что для каждого i < j < k < l , если i- я вершина в упорядочении смежна с k -й и l -й вершинами, а j -я и k -я вершины смежны, то j -я и l -я вершины также должны быть смежными. [3]
Граф является сильно хордальным тогда и только тогда, когда каждый из его индуцированных подграфов имеет простую вершину, вершину, окрестности которой имеют окрестности, линейно упорядоченные по включению. [4] Кроме того, граф является сильно хордальным тогда и только тогда, когда он хордальный и каждый цикл длины пять или более имеет двуххордовый треугольник, треугольник, образованный двумя хордами и ребром цикла. [5]
Граф является сильно хордальным тогда и только тогда, когда каждый из его индуцированных подграфов является дуально хордальным графом . [6]
Сильно хордальные графы также можно охарактеризовать с точки зрения количества полных подграфов, в которых участвует каждое ребро. [7] Дается еще одна характеристика. [8]
Признание
[ редактировать ], можно Определить, является ли граф строго хордальным за полиномиальное время путем многократного поиска и удаления простой вершины. Если этот процесс удаляет все вершины графа, граф должен быть строго хордальным; в противном случае, если этот процесс найдет подграф без каких-либо простых вершин, исходный граф не может быть строго хордальным. Для сильно хордального графа порядок удаления вершин в ходе этого процесса является сильным порядком полного исключения. [9]
Сейчас известны альтернативные алгоритмы, которые могут определить, является ли граф строго хордальным, и, если да, более эффективно построить сильное совершенное упорядочение исключения за время O(min( n 2 , ( n + m ) log n )) для графа с n вершинами и m ребрами. [10]
Подклассы
[ редактировать ]Важным подклассом (основанным на филогении ) является класс степеней k - листов , графов, образованных из листьев дерева путем соединения двух листьев ребром, когда их расстояние в дереве не превышает k . Степень листа — это граф, который является степенью k -листа для некоторого k .Поскольку степени сильно хордальных графов сильно хордальны, а деревья сильно хордальны, отсюда следует, что степени листьев сильно хордальны. Они образуют собственный подкласс сильно хордальных графов,который, в свою очередь, включает кластерные графы как степени двух листьев. [11] Другим важным подклассом сильно хордальных графов являются графы интервалов . В [12] показано, что графы интервалов и более широкий класс корневых ориентированных графов путей являются степенями листьев.
Алгоритмические задачи
[ редактировать ]Поскольку сильно хордальные графы являются одновременно хордальными и дуально хордальными графами , различные NP-полные задачи, такие как независимое множество, клика, раскраска, кликовое покрытие, доминирующее множество и дерево Штейнера, могут эффективно решаться для сильно хордальных графов. Изоморфизм графов изоморфно-полен для сильно хордальных графов. [13] Гамильтонова схема остается NP-полной для сильно хордальных расщепляемых графов . [14]
Примечания
[ редактировать ]- ^ Брандштедт, Ле и Спинрад (1999) , Определение 3.4.1, стр. 43.
- ^ Чанг (1982) ; Фарбер (1983) ; Брандштедт, Ле и Спинрад (1999) , теорема 7.2.1, с. 112.
- ^ Фарбер (1983) ; Брандштедт, Ле и Спинрад (1999) , теорема 5.5.1, с. 77.
- ^ Фарбер (1983) ; Брандштедт, Ле и Спинрад (1999) , теорема 5.5.2, с. 78.
- ^ Дальхаус, Мануэль и Миллер (1998) .
- ^ Брандштадт и др. (1998) , Следствие 3, с. 444
- ^ Макки (1999)
- ^ Де Кариа и Макки (2014)
- ^ Фарбер (1983) .
- ^ Любив (1987) ; Пейдж и Тарьян (1987) ; Спинрад (1993) .
- ^ Нисимура, Рагде и Тиликос (2002)
- ^ Брандштедт и др. (2010)
- ^ Уэхара, Тода и Нагоя (2005)
- ^ Мюллер (1996)
Ссылки
[ редактировать ]- Брандштедт, Андреас ; Драган, Федор; Чепой, Виктор; Волошин, Виталий (1998), «Двуххордальные графы», SIAM Journal on Discrete Mathematics , 11 (3): 437–455, doi : 10.1137/s0895480193253415 .
- Брандштедт, Андреас ; Хундт, Кристиан; Манчини, Федерико; Вагнер, Питер (2010), «Графы направленных путей с корнем являются степенями листьев», Discrete Mathematics , 310 (4): 897–910, doi : 10.1016/j.disc.2009.10.006 .
- Брандштедт, Андреас ; Ле, Ван Банг (2006), «Распознавание структуры и линейного времени трехлистных степеней», Information Processing Letters , 98 (4): 133–138, doi : 10.1016/j.ipl.2006.01.004 .
- Брандштедт, Андреас ; Ле, Ван Банг; Шритаран, Р. (2008), «Распознавание структуры и линейного времени четырехлистных степеней», Транзакции ACM по алгоритмам , 5 : Статья 11, doi : 10.1145/1435375.1435386 , S2CID 6114466 .
- Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-Х .
- Чанг, Дж. Дж. (1982), K -доминирование и проблемы покрытия графов , доктор философии. диссертация, Корнельский университет .
- Дальхаус, Э.; Мануэль, доктор медицинских наук; Миллер, М. (1998), «Характеристика сильно хордальных графов», Discrete Mathematics , 187 (1–3): 269–271, doi : 10.1016/S0012-365X(97)00268-9 .
- Де Кариа, П.; Макки, Т. А. (2014), «Максклика и характеристики единичного диска сильно хордальных графов», Дискуссии Mathematicae Graph Theory , 34 (3): 593–602, doi : 10.7151/dmgt.1757 , hdl : 11336/32705 .
- Фарбер, М. (1983), «Характеристики сильно хордальных графов», Discrete Mathematics , 43 (2–3): 173–189, doi : 10.1016/0012-365X(83)90154-1 .
- Любив, А. (1987), «Двойной лексический порядок матриц», SIAM Journal on Computing , 16 (5): 854–879, doi : 10.1137/0216057 .
- Макки, Т. А. (1999), «Новая характеристика сильно хордальных графов», Discrete Mathematics , 205 (1–3): 245–247, doi : 10.1016/S0012-365X(99)00107-7 .
- Мюллер, Х. (1996), «Гамильтоновы схемы в хордальных двудольных графах», Discrete Mathematics , 156 (1–3): 291–298, doi : 10.1016/0012-365x(95)00057-4 .
- Нисимура, Н.; Рагде, П.; Тиликос, Д.М. (2002), «О степенях графа для деревьев с помеченными листьями», Журнал алгоритмов , 42 : 69–108, doi : 10.1006/jagm.2001.1195 .
- Пейдж, Р.; Тарьян, Р.Э. (1987), «Алгоритмы уточнения трех разделов», SIAM Journal on Computing , 16 (6): 973–989, doi : 10.1137/0216062 , S2CID 33265037 .
- Раутенбах, Д. (2006), «Некоторые замечания о корнях листьев», Discrete Mathematics , 306 (13): 1456–1461, doi : 10.1016/j.disc.2006.03.030 .
- Спинрад, Дж. (1993), «Двойной лексический порядок плотных матриц 0–1», Information Processing Letters , 45 (2): 229–235, doi : 10.1016/0020-0190(93)90209-R .
- Уэхара, Р.; Тода, С.; Нагоя, Т. (2005), «Полнота изоморфизма графов для хордальных двудольных и сильно хордальных графов», Discrete Applied Mathematics , 145 (3): 479–482, doi : 10.1016/j.dam.2004.06.008 .