Двойственно хордальный граф

Неориентированный граф G двойственно хордален, если гиперграф его максимальных клик является гипердеревом^[англ.]. Имя происходит из факта, что граф хордален тогда и только тогда, когда гиперграф его максимальных клик двойственен гипердереву. Первоначально эти графы были определены по максимальному соседству и имеют ряд различных описаний^[1][2][3]. В отличие от хордальных графов свойство двойственной хордальности не наследуется, то есть, порождённые подграфы двойственного хордального графа не обязательно двойственно хордальны (в смысле наследства двойственно хордальные графы являются в точности наследниками строго хордальных графов), и двойственно хордальный граф в общем случае не совершенный. Двойственно хордальные графы появились первоначально под именем HT-графы^[4][5][6].

Двойственно хордальные графы являются графами клик хордальных графов^[7][8], то есть, графами пересечений максимальных клик хордальных графов.

Следующие свойства эквивалентны^{[1][2][9][5][6]}:

• G имеет упорядочения максимального соседства (англ. maximum neighborhood ordering)^[10].
• Есть остовное дерево T графа G такое, что любая максимальная клика графа G порождает поддерево в T.
• Гиперграф замкнутого соседства N(G) графа G является гипердеревом^[англ.].
• Гиперграф максимальных клик графа G является гипердеревом^[англ.].
• G является 2-секционным графом гипердерева^[англ.].

Из условия на гиперграф замкнутого соседства также следует, что граф двойственно хордален тогда и только тогда, когда его квадрат хордален и его гиперграф замкнутого соседства имеет свойство Хелли.

В статье Де Кариа и Гутирреза^[11] двойственные хордальные графы описываются в терминах свойств сепараторов. В статье Брешара^[12] показано, что двойственные хордальные графы являются в точности графами пересечений максимальных гиперкубов графов ацикличных кубических комплексов.

Структуру и алгоритмическое использование дважды хордальных графов дала Марина Москарини^[13]. Это хордальные графы, являющиеся одновременно и двойственно хордальными.

Двойственно хордальные графы могут быть распознаны за линейное время, а также упорядочение максимального соседства двойственного хордального графа может быть найдено за линейное время^[2][4].

В то время как основные задачи, такие как поиск максимального независимого множества, максимальной клики, раскраски и кликового покрытия остаются NP-полными для двойственных хордальных графов, некоторые варианты задачи о минимальном доминирующем множестве и дереве Штейнера эффективно решаются для двойственных хордальных графов (но задача независимого доминирования остаётся NP-полной)^[2][5][6]. См. статью Бранштэдта, Чепоя и Драгана^[14] для использования свойств двойственных хордальных графов для задач с остовными деревьями, и статью Бранштэдта, Ляйтерта и Раутенбаха^[15] для алгоритма линейного времени поиска доминирования вершин и рёбер.

• Terry A. McKee, McMorris F. R. Topics in Intersection Graph Theory. — SIAM Monographs on Discrete Mathematics and Applications, 1999.

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (31 января 2019) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (31 января 2019) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.