Хордальный двудольный граф

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

Описание

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

По определению хордальные двудольные графы имеют характеризацию запрещёнными подграфами как графы, не содержащие какого-либо порождённого пути длины 3 или длины по меньшей мере 5 (так называемые дыры) в качестве порождённого подграфа. Таким образом, граф G является хордальным двудольным тогда и только тогда, когда G не имеет треугольников и дыр. В статье Шаблон:Iw Шаблон:Sfn упоминаются две других характеризации:

B является хордальным двудольным тогда и только тогда, когда любой минимальный рёберный сепаратор^[1] порождает полный двудольный подграф в B и тогда и только тогда, когда любой порождённый подграф является совершенным исключением двудольного графа.

Мартин Фарбер показал, что граф строго хордален тогда и только тогда, когда двудольный граф инцидентности его гиперграфа максимальных клик^[2] является хордальным двудольнымШаблон:Sfn Шаблон:Sfn.

Аналогичная характеризация имеет место для гиперграфов замкнутых окрестностей — граф сильно хордален тогда и только тогда, когда двудольный граф инцидентности его гиперграфа замкнутых окрестностей^[3] является хордальным двудольнымШаблон:Sfn.

Другой результат, найденный Элиасом Далхаусом:

Двудольный граф

B = (X, Y, E)

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

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

Различные результаты описывают связь между хордальными двудольными графами и вполне сбалансированными гиперграфами окрестностей^[4] двудольных графовШаблон:Sfn.

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

Двудольный граф является хордальным двудольным тогда и только тогда, когда его матрица смежности Шаблон:Не переведено 5 Шаблон:Sfn.

Распознавание

Хордальные двудольные графы могут быть распознаны за время $O (\min (n^{2}, (n + m) \log n))$ для графов с n вершинами и m рёбрамиШаблон:Sfn Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn.

Сложность задач

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

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

Связанные классы графов

Любой хордальный двудольный граф является модулярным графом. Хордальные двудольные графы включают полные двудольные графы и двудольные дистанционно-наследуемые графы^[5].

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

↑ Рёберный сепаратор — это множество рёбер графа, удаление которых разбивает граф на два не связанных друг с другом подграфа. Обычно при этом накладывается ограничение, что каждый из получившихся подграфов содержит не более 2N/3 вершин (Planar Separator Theorem — Constructions — Edge Separators Шаблон:Wayback)
↑ Пусть имеется граф G. Гиперграф на тех же вершинах, гиперрёбрами которого служат максимальные клики графа G, называется гипреграфом максимальных клик (Шаблон:Harv).
↑ Если дан граф $G = (V, E)$ , окрестностью вершины $x \in V$ определяется как $N_{G} (x) = N (x) = {y \in V | (x, y) \in E}$ . Множество $N (x)$ часто называется открытой окрестностью вершины x, подчёркивая факт, что $x \notin V$ в графе без циклов. Соответственно, множество $N_{G} [x] = N [x] = N (x) \cup {x}$ называется замкнутой окрестностью вершины x. На вершинах V можно определить два гиперграфа, положив $N (G) = {N (x) | x \in V}$ и $N [G] = {N [x] | x \in V}$ . Первый гиперграф называется гиперграфом открытых окрестностей графа G. Второй гиперграф называется гиперграфом замкнутых окрестностей графа G Шаблон:Harv.
↑ Цикл $(x_{1}, E_{1}, \dots, x_{p}, E_{p})$ гиперграфа $H (x_{i} \in V (H), E_{i} \in E (H) | i = 1, \dots, p)$ называется специальным циклом гиперграфа H. Гиперграф называется сбалансированным, если он не содержит специальных циклов нечётной длины. Шаблон:Harv
↑ Chordal bipartite graphs Шаблон:Wayback, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

[1] Рёберный сепаратор — это множество рёбер графа, удаление которых разбивает граф на два не связанных друг с другом подграфа. Обычно при этом накладывается ограничение, что каждый из получившихся подграфов содержит не более 2N/3 вершин (Planar Separator Theorem — Constructions — Edge Separators Шаблон:Wayback)

[2] Пусть имеется граф G. Гиперграф на тех же вершинах, гиперрёбрами которого служат максимальные клики графа G, называется гипреграфом максимальных клик (Шаблон:Harv).

[3] Если дан граф $G = (V, E)$ , окрестностью вершины $x \in V$ определяется как $N_{G} (x) = N (x) = {y \in V | (x, y) \in E}$ . Множество $N (x)$ часто называется открытой окрестностью вершины x, подчёркивая факт, что $x \notin V$ в графе без циклов. Соответственно, множество $N_{G} [x] = N [x] = N (x) \cup {x}$ называется замкнутой окрестностью вершины x. На вершинах V можно определить два гиперграфа, положив $N (G) = {N (x) | x \in V}$ и $N [G] = {N [x] | x \in V}$ . Первый гиперграф называется гиперграфом открытых окрестностей графа G. Второй гиперграф называется гиперграфом замкнутых окрестностей графа G Шаблон:Harv.

[4] Цикл $(x_{1}, E_{1}, \dots, x_{p}, E_{p})$ гиперграфа $H (x_{i} \in V (H), E_{i} \in E (H) | i = 1, \dots, p)$ называется специальным циклом гиперграфа H. Гиперграф называется сбалансированным, если он не содержит специальных циклов нечётной длины. Шаблон:Harv

[Cbg-5] Chordal bipartite graphs Шаблон:Wayback, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

[1]

[2]

[3]

[4]

[5]

Хордальный двудольный граф

Содержание

Описание

Распознавание

Сложность задач

Связанные классы графов

Примечания

Литература

Навигация

Хордальный двудольный граф

Описание

Распознавание

Сложность задач

Связанные классы графов

Примечания

Литература

Навигация

Поиск