Гипердерево

Чтобы узнать о других значениях, см. Гипердерево (значения) .

Гипердерево (синие вершины и желтые гиперребра) и его хост-дерево (красное)

В математической области теории графов гиперграф если H называется гипердеревом, он допускает главный граф T такой, что T является деревом . Другими словами, H является гипердеревом, если существует дерево такое , что каждое гиперребро H T является множеством вершин связного поддерева T . Гипердеревья также называют древесными гиперграфами. или древовидные гиперграфы .

Каждое дерево T само по себе является гипердеревом: само T можно использовать в качестве главного графа, а каждое ребро T является поддеревом этого главного графа. Следовательно, гипердеревья можно рассматривать как обобщение понятия дерева для гиперграфов . К ним относятся связные ациклические по Бержу гиперграфы, которые также использовались как (другое) обобщение деревьев для гиперграфов.

Характеристики

Каждое гипердерево обладает свойством Хелли (свойством 2-Хелли): если подмножество S его гиперребер обладает свойством, что каждые два гиперребра в S имеют непустое пересечение , то само S имеет непустое пересечение (вершину, принадлежащую всем гиперребрам в S). С ).

По результатам Дюше, Фламана и Слейтера Гипердеревья можно эквивалентно охарактеризовать следующими способами.

• Гиперграф H является гипердеревом тогда и только тогда, когда он обладает свойством Хелли и его линейный граф является хордальным графом .
• Гиперграф H является гипердеревом тогда и только тогда, когда его двойственный гиперграф H ^* конформен , а двухсекционный граф H ^* является хордальным.
• Гиперграф является гипердеревом тогда и только тогда, когда его двойственный гиперграф альфа-ацикличен в смысле Феджина.

Гипердеревья (как двойственные альфа-ациклические гиперграфы) можно распознать за линейное время . Задача точного покрытия (нахождение набора непересекающихся гиперребер, покрывающего все вершины) разрешима за полиномиальное время для гипердеревьев, но остается NP-полной для альфа-ациклических гиперграфов.

См. также

• Дуально хордальный граф — граф, максимальные клики которого образуют гипердерево.

Ссылки

• Берге, Клод (1989), Гиперграфы: комбинаторика конечных множеств , Математическая библиотека Северной Голландии, том. 45, Амстердам: Северная Голландия, ISBN  0-444-87489-5 , МР   1013569 .
• Брандштедт, Андреас ; Драган, Федор; Чепой, Виктор; Волошин, Виталий (1998), «Двуххордальные графы» (PDF) , SIAM Journal on Discrete Mathematics , 11 : 437–455, doi : 10.1137/s0895480193253415 , MR   1628114 .
• Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN  0-89871-432-Х , МР   1686154 .
• Брандштедт, Андреас ; Лейтерт, Арне; Раутенбах, Дитер (2012), «Эффективные доминирующие и доминирующие по ребрам множества для графов и гиперграфов», Алгоритмы и вычисления: 23-й международный симпозиум, ISAAC 2012, Тайбэй, Тайвань, 19–21 декабря 2012 г., Труды , Конспекты лекций по информатике , том. 7676, стр. 267–277, arXiv : 1207.0953 , doi : 10.1007/978-3-642-35261-4_30 , MR   3065639 .
• Феджин, Рональд (1983), «Степени ацикличности гиперграфов и схем реляционных баз данных», Журнал ACM , 30 : 514–550, doi : 10.1145/2402.322390 , MR   0709831 .
• Макки, штат Калифорния; МакМоррис, Франция (1999), Темы теории графов пересечений , Монографии SIAM по дискретной математике и ее приложениям, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики, ISBN  0-89871-430-3 , МР   1672910 .
• Тарьян, Роберт Э .; Яннакакис, Михалис (1984), «Простые алгоритмы линейного времени для проверки хордльности графов, проверки ацикличности гиперграфов и выборочного сокращения ациклических гиперграфов» (PDF) , SIAM Journal on Computing , 13 (3): 566–579, doi : 10.1137/0213035 , МР   0749707 .
• Волошин, Виталий (2002), Раскраска смешанных гиперграфов: теория, алгоритмы и приложения , Монографии Института Филдса, том. 17, Провиденс, Род-Айленд: Американское математическое общество, ISBN.  0-8218-2812-6 , МР   1912135 .