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

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

Описание

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

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

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

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

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

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

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

B=(X,Y,E)

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

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

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

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

Двудольный граф является хордальным двудольным тогда и только тогда, когда его матрица смежности полностью уравновешена^[англ.]^[6].

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

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

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

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

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

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

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

Примечания

↑ Golumbic, 1980, с. 261.
↑ Brandstädt, Le, Spinrad, 1999, с. 43 Definition 3.4.1.
↑ Golumbic, 1980.
↑ Рёберный сепаратор — это множество рёбер графа, удаление которых разбивает граф на два не связанных друг с другом подграфа. Обычно при этом накладывается ограничение, что каждый из получившихся подграфов содержит не более 2N/3 вершин (Planar Separator Theorem — Constructions — Edge Separators Архивная копия от 18 августа 2019 на Wayback Machine)
↑ Пусть имеется граф G. Гиперграф на тех же вершинах, гиперрёбрами которого служат максимальные клики графа G, называется гипреграфом максимальных клик ((Gravier, Škrekovski 2001, 1)).
↑ ¹ ² Farber, 1983.
↑ Brandstädt, Le, Spinrad, 1999, с. 43 Theorem 3.4.1.
↑ Если дан граф $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 (Boros, Gurvich, Zverovich 2006, 7, 2.3 Neighborhood hypergraphs).
↑ Brandstädt, 1991.
↑ Brandstädt, Le, Spinrad, 1999, с. 129 Corollary 8.3.2.
↑ Dragan, Voloshin, 1996.
↑ Цикл $(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. Гиперграф называется сбалансированным, если он не содержит специальных циклов нечётной длины. (Lehel, Tuza 1986, 96)
↑ Brandstädt, Le, Spinrad, 1999, с. 126–127 Theorems 8.2.5, 8.2.6.
↑ Huang, 2006.
↑ Lubiw, 1987.
↑ Paige, Tarjan, 1987.
↑ Spinrad, 1993.
↑ ¹ ² Spinrad, 2003.
↑ Müller, 1996.
↑ Müller, Brandstädt, 1987.
↑ Lu, Tang, 2002.
↑ Chordal bipartite graphs Архивная копия от 24 августа 2019 на Wayback Machine, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

Литература

Sylvain Gravier, Riste Škrekovski. COLORING THE CLIQUE HYPERGRAPH OF GRAPHS WITHOUT FORBIDDEN STRUCTURE // Preprint series. — Jadranska 19, 1111 Ljubljana, Slovenia: University of Ljubljana, Institute of Mathematics, Physics and Mechanics, 2001. — Т. 41 (2003), 890. — ISSN 1318-4865.
Endre Boros, Vladimir Gurvich, Igor Zverovich. 2.3 Neighborhood hypergraphs // Neighborhood hypergraphs of bipartite graphs. — 2006. — Т. RRR 12-2006,. — (Rutcor Research Report).
J. Lehel, Zs Tuza. NEIGHBORHOOD PERFECT GRAPHS // Discrete Mathematics. — North-Holland, 1986. — Т. 61. — С. 93—101.
Andreas Brandstädt. Classes of bipartite graphs related to chordal graphs // Discrete Applied Mathematics. — 1991. — Т. 32. — С. 51–60. — doi:10.1016/0166-218x(91)90023-p.
Andreas Brandstädt, Feodor Dragan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // SIAM Journal on Discrete Mathematics. — 1998. — Т. 11. — С. 437–455. — doi:10.1137/s0895480193253415.
Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X.
Feodor Dragan, Vitaly Voloshin. Incidence graphs of biacyclic hypergraphs // Discrete Applied Mathematics. — 1996. — Т. 68. — С. 259–266. — doi:10.1016/0166-218x(95)00070-8.
Farber M. Characterizations of strongly chordal graphs // Discrete Mathematics. — 1983. — Т. 43, вып. 2–3. — С. 173–189. — doi:10.1016/0012-365X(83)90154-1.
Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — ISBN 0-12-289260-7.
Jing Huang. Representation characterizations of chordal bipartite graphs // Journal of Combinatorial Theory, Series B. — 2006. — Т. 96, вып. 5. — С. 673–683. — doi:10.1016/j.jctb.2006.01.001.
Chin Lung Lu, Chuan Yi Tang. Weighted efficient domination on some perfect graphs // Discrete Applied Mathematics. — 2002. — Т. 117. — С. 163–182. — doi:10.1016/s0166-218x(01)00184-6.
Anna Lubiw. Doubly lexical orderings of matrices // SIAM Journal on Computing. — 1987. — Т. 16, вып. 5. — С. 854–879. — doi:10.1137/0216057.
Haiko Müller. Hamilton circuits in chordal bipartite graphs // Discrete Mathematics. — 1996. — Т. 156. — С. 291–298. — doi:10.1016/0012-365x(95)00057-4.
Haiko Müller, Andreas Brandstädt. The NP-completeness of Steiner Tree and Dominating Set for chordal bipartite graphs // Theoretical Computer Science. — 1987. — Т. 53. — С. 257–265. — doi:10.1016/0304-3975(87)90067-3.
Paige R., Tarjan R. E. Three partition refinement algorithms // SIAM Journal on Computing. — 1987. — Т. 16, вып. 6. — С. 973–989. — doi:10.1137/0216062.
Jeremy Spinrad. Doubly lexical ordering of dense 0–1 matrices // Information Processing Letters. — 1993. — Т. 45, вып. 2. — С. 229–235. — doi:10.1016/0020-0190(93)90209-R.
Jeremy Spinrad. Efficient Graph Representations. — Fields Institute Monographs, American Mathematical Society, 2003. — ISBN 0-8218-2815-0.

[_e50488fcd979d2ee-1] Golumbic, 1980, с. 261.

[_4ab4c17cf7dd30bc-2] Brandstädt, Le, Spinrad, 1999, с. 43 Definition 3.4.1.

[_d0dc4be937ac5c21-3] Golumbic, 1980.

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

[5] Пусть имеется граф G. Гиперграф на тех же вершинах, гиперрёбрами которого служат максимальные клики графа G, называется гипреграфом максимальных клик ((Gravier, Škrekovski 2001, 1)).

[_2bbea2a8987a88ee-6] ¹ ² Farber, 1983.

[_3692b09dc9b01991-7] Brandstädt, Le, Spinrad, 1999, с. 43 Theorem 3.4.1.

[8] Если дан граф $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 (Boros, Gurvich, Zverovich 2006, 7, 2.3 Neighborhood hypergraphs).

[_69d239077061d6f6-9] Brandstädt, 1991.

[_82736e505ef05c70-10] Brandstädt, Le, Spinrad, 1999, с. 129 Corollary 8.3.2.

[_3ba5ba1debc26455-11] Dragan, Voloshin, 1996.

[12] Цикл $(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. Гиперграф называется сбалансированным, если он не содержит специальных циклов нечётной длины. (Lehel, Tuza 1986, 96)

[_49b287ecb2c9a66e-13] Brandstädt, Le, Spinrad, 1999, с. 126–127 Theorems 8.2.5, 8.2.6.

[_d36b2acac3c2e05a-14] Huang, 2006.

[_2c828f72903ff359-15] Lubiw, 1987.

[_279f4bf7e867903c-16] Paige, Tarjan, 1987.

[_9ab7ce9a95db6f2a-17] Spinrad, 1993.

[_251a11bd553026cd-18] ¹ ² Spinrad, 2003.

[_0a5160b4fbd8ec37-19] Müller, 1996.

[_c0aa0887fc562398-20] Müller, Brandstädt, 1987.

[_e07e84c71216323a-21] Lu, Tang, 2002.

[Cbg-22] Chordal bipartite graphs Архивная копия от 24 августа 2019 на Wayback Machine, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

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

Содержание

Описание

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

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

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

Примечания

Литература

Навигация

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

Описание

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

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

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

Примечания

Литература

Навигация

Поиск