Неориентированный граф G двойственно хордален, если гиперграф его максимальных клик является . Имя происходит из факта, что граф хордален тогда и только тогда, когда гиперграф его максимальных клик двойственен гипердереву. Первоначально эти графы были определены по максимальному соседству и имеют ряд различных описаний. В отличие от хордальных графов свойство двойственной хордальности не наследуется, то есть, порождённые подграфы двойственного хордального графа не обязательно двойственно хордальны (в смысле наследства двойственно хордальные графы являются в точности наследниками строго хордальных графов), и двойственно хордальный граф в общем случае не совершенный. Двойственно хордальные графы появились первоначально под именем HT-графы.
Описание Двойственно хордальные графы являются графами клик хордальных графов, то есть, графами пересечений максимальных клик хордальных графов.
Следующие свойства эквивалентны: G имеет упорядочения максимального соседства ()Понятие упорядочения максимального соседства не тривиально, в статье (Brandstädt, Dragan, Chepoi, Voloshin, 1998, стр. 440—442) оно занимает 2 страницы. Есть остовное дерево T графа G такое, что любая максимальная клика графа G порождает поддерево в T. Гиперграф замкнутого соседства N(G) графа G является . Гиперграф максимальных клик графа G является . G является 2-секционным графом .
Из условия на гиперграф замкнутого соседства также следует, что граф двойственно хордален тогда и только тогда, когда его квадрат хордален и его гиперграф замкнутого соседства имеет свойство Хелли.
В статье Де Кариа и Гутирреза двойственные хордальные графы описываются в терминах свойств сепараторов. В статье Брешара показано, что двойственные хордальные графы являются в точности графами пересечений максимальных гиперкубов графов ацикличных кубических комплексов.
Структуру и алгоритмическое использование дважды хордальных графов дала Марина Москарини. Это хордальные графы, являющиеся одновременно и двойственно хордальными.
Распознавание Двойственно хордальные графы могут быть распознаны за линейное время, а также упорядочение максимального соседства двойственного хордального графа может быть найдено за линейное время.
Сложность проблем В то время как основные задачи, такие как поиск максимального независимого множества, максимальной клики, раскраски и кликового покрытия остаются NP-полными для двойственных хордальных графов, некоторые варианты задачи о минимальном доминирующем множестве и дереве Штейнера эффективно решаются для двойственных хордальных графов (но задача независимого доминирования остаётся NP-полной). См. статью Бранштэдта, Чепоя и Драгана для использования свойств двойственных хордальных графов для задач с остовными деревьями, и статью Бранштэдта, Ляйтерта и Раутенбаха для алгоритма линейного времени поиска доминирования вершин и рёбер.
Примечания
Литература
Категория:Семейства графов Категория:Совершенные графы