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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

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

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

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

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

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

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

[править | править код]

Хордальные двудольные графы могут быть распознаны за время для графов с n вершинами и m рёбрами[15][16][17][18].

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

[править | править код]

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

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

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

[править | править код]

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

Примечания

[править | править код]
  1. Golumbic, 1980, с. 261.
  2. Brandstädt, Le, Spinrad, 1999, с. 43 Definition 3.4.1.
  3. Golumbic, 1980.
  4. Рёберный сепаратор — это множество рёбер графа, удаление которых разбивает граф на два не связанных друг с другом подграфа. Обычно при этом накладывается ограничение, что каждый из получившихся подграфов содержит не более 2N/3 вершин (Planar Separator Theorem — Constructions — Edge Separators Архивная копия от 18 августа 2019 на Wayback Machine)
  5. Пусть имеется граф G. Гиперграф на тех же вершинах, гиперрёбрами которого служат максимальные клики графа G, называется гипреграфом максимальных клик ((Gravier, Škrekovski 2001, 1)).
  6. 1 2 Farber, 1983.
  7. Brandstädt, Le, Spinrad, 1999, с. 43 Theorem 3.4.1.
  8. Если дан граф , окрестностью вершины определяется как . Множество часто называется открытой окрестностью вершины x, подчёркивая факт, что в графе без циклов. Соответственно, множество называется замкнутой окрестностью вершины x. На вершинах V можно определить два гиперграфа, положив и . Первый гиперграф называется гиперграфом открытых окрестностей графа G. Второй гиперграф называется гиперграфом замкнутых окрестностей графа G (Boros, Gurvich, Zverovich 2006, 7, 2.3 Neighborhood hypergraphs).
  9. Brandstädt, 1991.
  10. Brandstädt, Le, Spinrad, 1999, с. 129 Corollary 8.3.2.
  11. Dragan, Voloshin, 1996.
  12. Цикл гиперграфа называется специальным циклом гиперграфа H. Гиперграф называется сбалансированным, если он не содержит специальных циклов нечётной длины. (Lehel, Tuza 1986, 96)
  13. Brandstädt, Le, Spinrad, 1999, с. 126–127 Theorems 8.2.5, 8.2.6.
  14. Huang, 2006.
  15. Lubiw, 1987.
  16. Paige, Tarjan, 1987.
  17. Spinrad, 1993.
  18. 1 2 Spinrad, 2003.
  19. Müller, 1996.
  20. Müller, Brandstädt, 1987.
  21. Lu, Tang, 2002.
  22. 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.