Дуально хордовый граф
В математической области теории графов неориентированный граф G является дуально хордальным , если гиперграф его максимальных клик является гипердеревом . Название происходит от того факта, что граф является хордальным тогда и только тогда, когда гиперграф его максимальных клик является двойственным гипердереву. Первоначально эти графы определялись максимальными соседними порядками и имели множество различных характеристик. [1] В отличие от хордовых графов, свойство быть дуально хордальным не является наследственным, т. е. индуцированные подграфы дуально хордального графа не обязательно являются дуально хордальными (наследственно дуально хордальные графы являются в точности сильно хордальными графами ), а дуально хордальный граф в общем случае не является совершенным графом .
Дуально-хордовые графы впервые появились под названием HT-графы . [2]
Характеристика
Дуально хордовые графы — это графы клик хордовых графов , [3] т.е. графы пересечений максимальных клик хордовых графов.
Следующие свойства эквивалентны: [4]
- G имеет максимальный порядок соседства.
- Существует остовное дерево T графа G, такое что любая максимальная клика графа G порождает поддерево T.
- Замкнутый гиперграф соседства N(G) графа G является гипердеревом .
- Максимальный кликовый гиперграф графа G является гипердеревом .
- G — это 2-секционный граф гипердерева .
Условие на замкнутый окрестностный гиперграф также подразумевает, что граф является дуально хордальным тогда и только тогда, когда его квадрат хордален, а его замкнутый окрестностный гиперграф обладает свойством Хелли .
В работе De Caria & Gutierrez (2012) дуально хордальные графы характеризуются в терминах свойств сепаратора. В работе Brešar (2003) было показано, что дуально хордальные графы являются в точности графами пересечений максимальных гиперкубов графов ациклических кубических комплексов.
Структура и алгоритмическое использование дважды хордовых графов даны Москарини (1993). Это графы, которые являются хордовыми и дуально хордовыми.
Признание
Дуально хордовые графы можно распознать за линейное время, а максимальный порядок соседства дуально хордового графа можно найти за линейное время. [5]
Сложность проблем
В то время как некоторые базовые проблемы, такие как максимальное независимое множество , максимальная клика , раскраска и покрытие кликой остаются NP-полными для дуально хордовых графов, некоторые варианты проблемы минимального доминирующего множества и дерева Штейнера эффективно решаются на дуально хордовых графах (но независимое доминирование остается NP-полным ). [6] См. Brandstädt, Chepoi & Dragan (1999) для использования свойств дуально хордового графа для остовных деревьев и см. Brandstädt, Leitert & Rautenbach (2012) для линейного алгоритма эффективного доминирования и эффективного доминирования ребер на дуально хордовых графах.
Примечания
- ^ Брандштедт и др. (1998); Брандштедт, Ле и Спинрад (1999)
- ^ Драган (1989); Драган, Присакару и Чепой (1992); Драган (1993)
- ^ Гутьеррес и Обина (1996); Шварцфитер и Борнштейн (1994)
- ^ Брандштедт, Чепой и Драган (1998); Брандштедт и др. (1998); Драган, Присакару и Чепой (1992); Драган (1993)
- ^ Брандштадт, Чепой и Драган (1998); Драган (1989)
- ^ Брандштедт, Чепой и Драган (1998); Драган, Присакару и Чепой (1992); Драган (1993)
Ссылки
- Брандштедт, Андреас; Чепои, Виктор; Драган, Федор (1998), «Алгоритмическое использование структуры гипердерева и упорядочения максимального соседства», Дискретная прикладная математика , 82 (1–3): 43–77, doi : 10.1016/s0166-218x(97)00125-x.
- Брандштедт, Андреас; Чепои, Виктор; Драган, Федор (1999), «Деревья аппроксимации расстояний для хордовых и дуально хордовых графов», Журнал алгоритмов , 30 : 166–184, doi :10.1006/jagm.1998.0962.
- Брандштедт, Андреас; Драган, Федор; Чепой, Виктор; Волошин, Виталий (1998), "Двойственно хордовые графы", SIAM Journal on Discrete Mathematics , 11 (3): 437–455, doi :10.1137/S0895480193253415, MR 1628114.
- Брандштедт, Андреас; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: Обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
- Brandstädt, Andreas; Leitert, Arne; Rautenbach, Dieter (2012), "Эффективные доминирующие и доминирующие ребра множества для графов и гиперграфов", в Chao, Kun-Mao; Hsu, Tsan-sheng; Lee, Der-Tsai (ред.), Algorithms and Computation – 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19–21, 2012. Proceedings , Lecture Notes in Computer Science , vol. 7676, Springer, pp. 267–277, arXiv : 1207.0953 , doi :10.1007/978-3-642-35261-4_30.
- Брешар, Боштян (2003), «Графы пересечений максимальных гиперкубов», Европейский журнал комбинаторики , 24 (2): 195–209, doi : 10.1016/s0195-6698(02)00142-7.
- Де Кария, Пабло; Гутьеррес, Мариса (2012), «О минимальных разделителях вершин дуально хордальных графов: свойства и характеристики», Дискретная прикладная математика , 160 (18): 2627–2635, doi : 10.1016/j.dam.2012.02.022 , hdl : 11336/190841.
- Драган, Федор (1989), Центры графов и свойство Helly (на русском языке) , докторская диссертация, Молдавский государственный университет, Молдова.
- Драган, Федор; Присакару, Кирилл; Чепой, Виктор (1992), «Проблемы размещения в графах и свойство Хелли», Дискретная математика (Москва) , 4 : 67–73.
- Драган, Федор (1993), «HT-графы: центры, связное r-доминирование и деревья Штейнера», Журнал вычислительной техники Молдовы (Кишинев) , 1 : 64–83.
- Гутьеррес, Мариса; Убина, Л. (1996), «Метрические характеристики правильных интервальных графов и графов «дерево-клика»», Журнал теории графов , 21 (2): 199–205, doi :10.1002/(sici)1097-0118(199602)21:2<199::aid-jgt9>3.0.co;2-m.
- Макки, Терри А.; Макморрис, Ф.Р. (1999), Темы в теории графов пересечений , Монографии SIAM по дискретной математике и приложениям.
- Москарини, Марина (1993), «Двойные хордовые графы, деревья Штейнера и связанное доминирование», Сети , 23 : 59–69, doi :10.1002/net.3230230108.
- Шварцфитер, Джейми Л.; Борнштейн, Клодсон Ф. (1994), «Кликовые графы хордовых и траекторных графов», SIAM Journal on Discrete Mathematics , 7 (2): 331–336, CiteSeerX 10.1.1.52.521 , doi :10.1137/s0895480191223191.
