Хорда́льный двудо́льный граф — это двудольный граф , в котором любой цикл длины по меньшей мере 6 в B имеет хорду, то есть ребро, которое соединяет две вершины, находящиеся на расстоянии > 1. Следовало бы называть эти графы «слабо хордальными и двудольными», поскольку хордальные двудольные графы, вообще говоря, не хордальны, так как могут содержать порождённый путь длины 4.

Описание Хордальные двудольные графы имеют различное описание в терминах совершенных порядков исключения, гиперграфов и матриц. Они тесно связаны со строго хордальными графами.

По определению хордальные двудольные графы имеют характеризацию запрещёнными подграфами как графы, не содержащие какого-либо порождённого пути длины 3 или длины по меньшей мере 5 (так называемые дыры) в качестве порождённого подграфа. Таким образом, граф G является хордальным двудольным тогда и только тогда, когда G не имеет треугольников и дыр. В статье упоминаются две других характеризации: B является хордальным двудольным тогда и только тогда, когда любой минимальный рёберный сепараторРёберный сепаратор — это множество рёбер графа, удаление которых разбивает граф на два не связанных друг с другом подграфа. Обычно при этом накладывается ограничение, что каждый из получившихся подграфов содержит не более 2N/3 вершин (Planar Separator Theorem — Constructions — Edge Separators ) порождает полный двудольный подграф в B и тогда и только тогда, когда любой порождённый подграф является совершенным исключением двудольного графа.

Мартин Фарбер показал, что граф строго хордален тогда и только тогда, когда двудольный граф инцидентности его гиперграфа максимальных кликПусть имеется граф G. Гиперграф на тех же вершинах, гиперрёбрами которого служат максимальные клики графа G, называется гипреграфом максимальных клик (). является хордальным двудольным.

Аналогичная характеризация имеет место для гиперграфов замкнутых окрестностей — граф сильно хордален тогда и только тогда, когда двудольный граф инцидентности его гиперграфа замкнутых окрестностейЕсли дан граф , окрестностью вершины определяется как . Множество часто называется открытой окрестностью вершины x, подчёркивая факт, что в графе без циклов. Соответственно, множество называется замкнутой окрестностью вершины x. На вершинах V можно определить два гиперграфа, положив и . Первый гиперграф называется гиперграфом открытых окрестностей графа G. Второй гиперграф называется гиперграфом замкнутых окрестностей графа G . является хордальным двудольным.

Другой результат, найденный Элиасом Далхаусом: Двудольный граф является хордальным двудольным тогда и только тогда, когда расщепляемый граф, получающийся из превращения X в клику, является строго хордальным.

Двудольный граф B = (X,Y,E) является хордальным двудольным тогда и только тогда, когда любой порождённый подграф графа B имеет упорядочение максимального X-соседства и упорядочение максимального Y- соседства.

Различные результаты описывают связь между хордальными двудольными графами и вполне сбалансированными гиперграфами окрестностейЦикл гиперграфа называется специальным циклом гиперграфа H. Гиперграф называется сбалансированным, если он не содержит специальных циклов нечётной длины. двудольных графов.

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

Двудольный граф является хордальным двудольным тогда и только тогда, когда его матрица смежности .

Распознавание Хордальные двудольные графы могут быть распознаны за время для графов с n вершинами и m рёбрами.

Сложность задач Различные задачи, такие как поиск гамильтонова цикла, дерева Штейнера и эффективного доминирования, остаются NP-полными на хордальных двудольных графах.

Различные другие задачи, которые могут быть эффективно решены для двудольных графов, могут иметь более эффективное решение для хордальных двудольных графов, что обсуждается в статье Спинрада.

Связанные классы графов Любой хордальный двудольный граф является модулярным графом. Хордальные двудольные графы включают полные двудольные графы и двудольные дистанционно-наследуемые графыChordal bipartite graphs , Information System on Graph Classes and their Inclusions, retrieved 2016-09-30..

Примечания

Литература

Категория:Семейства графов Категория:Двудольные графы