В математической области теории графов , неориентированный граф G является двойственной хордой , если гиперграф ее максимального клика является гипердеревом . Название происходит от того факта, что граф является хордовым тогда и только тогда, когда гиперграф его максимальных клик является двойственным к гипердереву. Первоначально эти графы были определены максимальным порядком соседства и имеют множество различных характеристик. [1] В отличие от хордовых графов, свойство дуально-хордовых графов не является наследственным, т. Е. Индуцированные подграфы дуально-хордовых графов не обязательно являются дуально-хордовыми (наследственно дуально-хордовые графы - это в точностисильно хордовые графы ), а дуально-хордовый граф, вообще говоря, не является совершенным графом . Дуальнохордовые графы впервые появились под названием HT-графы . [2]
Характеристики [ править ]
Двойственно Хордовые графики являются клика графики из аккордовых графов , [3] то есть, пересечение графиков максимальных клик аккордовых графов.
Следующие свойства эквивалентны: [4]
- G имеет максимальный порядок соседства.
- Существует остовное дерево T из G таких , что любая максимальная клика G индуцирует поддерево в T .
- Замкнутая окрестность Гиперграф N (G) из G является гипердерево .
- Максимальный кликовый гиперграф группы G является гипердеревом .
- G - двухсекционный граф гипердерева .
Из условия на замкнутый соседний гиперграф также следует, что граф является дуально хордовым тогда и только тогда, когда его квадрат хордовый, а его замкнутый соседний гиперграф обладает свойством Хелли .
В De Caria & Gutierrez (2012) дуально-хордовые графы охарактеризованы с точки зрения свойств разделителей. В Brešar (2003) было показано, что дуально-хордовые графы - это в точности графы пересечений максимальных гиперкубов графов ациклических кубических комплексов.
Структура и алгоритмическое использование двухордовых графов даны Москарини (1993) . Это графики, которые бывают хордовыми и двойственно-хордовыми.
Признание [ править ]
Дуальнохордовые графы можно распознать за линейное время, а максимальное упорядочение окрестностей дуальнохордовых графов можно найти за линейное время. [5]
Сложность проблем [ править ]
В то время как некоторые основные проблемы, такие как максимальное независимое множество , максимальная клика , раскраска и покрытие клик, остаются NP-полными для двухордовых графов, некоторые варианты задачи о минимальном доминирующем множестве и дереве Штейнера эффективно разрешимы на двойственно-хордовых графах (но независимое доминирование остается NP -полный ). [6] См. Brandstädt, Chepoi & Dragan (1999) для использования свойств двухордового графа для гаечных ключей, и см. Brandstädt, Leitert & Rautenbach (2012) для алгоритма линейного времени эффективного доминирования и эффективное доминирование ребер на двойных хордовых графах.
Заметки [ править ]
- ^ Brandstädt et al. (1993) ; Brandstädt, Chepoi & Dragan (1994) ; Brandstädt et al. (1994) ; Brandstädt et al. (1998) ; Brandstädt, Le & Spinrad (1999)
- ^ Драган (1989) ; Драган, Присакару и Чепои (1992) ; Драган (1993)
- ^ Гутьеррес & Oubina (1996) ; Шварцфитер и Борнштейн (1994)
- ^ Brandstädt et al. (1993) ; Brandstädt, Chepoi & Dragan (1998) ; Brandstädt et al. (1998) ; Драган, Присакару и Чепои (1992) ; Драган (1993)
- ^ Brandstädt, Chepoi & Dragan (1998) ; Драган (1989)
- ^ Brandstädt, Chepoi & Dragan (1998) ; Драган, Присакару и Чепои (1992) ; Драган (1993)
Ссылки [ править ]
- Брандштадт, Андреас; Чепой, Виктор; Драган, Феодоры (1998), "алгоритмическое использование структуры гипердерева и максимальных упорядочения окрестностей", Дискретная прикладная математика , 82 : 43-77, DOI : 10.1016 / s0166-218x (97) 00125-х.
- Брандштадт, Андреас; Чепой, Виктор; Драган, Феодоры (1999), «Расстояние аппроксимирующих дерева для аккордовых и дуально аккордовых графов», журнал алгоритмов , 30 : 166-184, DOI : 10,1006 / jagm.1998.0962.
- Брандштадт, Андреас; Драган, Федор; Чепой, Виктор; Волошин, Виталий (1993), "Двойные хордовые графы", Конспект лекций по информатике , 790 : 237–251.
- Брандштадт, Андреас; Драган, Федор; Чепой, Виктор; Волошин Виталий (1998), "Двойственна хордальные Графы", SIAM журнал по дискретной математике , 11 : 437-455, DOI : 10,1137 / s0895480193253415.
- Брандштадт, Андреас; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
- Брандштадт, Андреас; Лейтерт, Арне; Раутенбах, Дитер (2012), «Эффективные доминирующие и доминирующие края множества для графов и гиперграфов», конспект лекций по информатике , 7676 : 267–277, arXiv : 1207.0953.
- Brešar, Boštjan (2003), "Пересечение графики максимальных гиперкуб", Европейский журнал комбинаторика , 24 : 195-209, DOI : 10.1016 / s0195-6698 (02) 00142-7.
- Де Кариа, Пабло; Гутьеррес, Мариса (2012), "О минимальных вершинных Сепараторах дуально Хордовых графов: Свойствах и характеризации", Дискретная прикладная математика , 160 : 2627-2635, DOI : 10.1016 / j.dam.2012.02.022.
- Драган, Федор (1989), Центры графов и свойство Хелли , канд. кандидатская диссертация, Молдавский Государственный Университет, Молдова.
- Драган, Федор; Присакару, Кирилл; Чепой, Виктор (1992), "Проблемы размещения в графах и свойство Хелли", Дискретная математика. (Москва) , 4 : 67–73.
- Драган, Федор (1993), "HT-графы: центры, связное r-доминирование и деревья Штейнера", Ж. вычисл. Sci. Ж. Молдовы (Кишинев) , 1 : 64–83..
- Гутьеррес, Мариса; Обина, Л. (1996), "Метрические характеристики собственных интервальных графов и древовидных графов", Журнал теории графов , 21 : 199–205, DOI : 10.1002 / (sici) 1097-0118 (199602) 21: 2 < 199 :: aid-jgt9> 3.0.co; 2-м.
- Макки, Терри А .; МакМоррис, Фр. (1999), Темы теории графов пересечений , Монографии SIAM по дискретной математике и приложениям.
- Moscarini, Марина (1993), "Вдвойне хордальные Графы, Steiner дерева и связное доминирование", сети , 23 : 59-69, DOI : 10.1002 / net.3230230108.
- Szwarcfiter, Jayme L .; Борнстейн, Claudson F. (1994), "Клик Графа Хордового и Path Графа", SIAM журнал по дискретной математике , 7 : 331-336, CiteSeerX 10.1.1.52.521 , DOI : 10,1137 / s0895480191223191.
