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

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

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

Описание[править | править код]

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

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

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

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

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

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

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

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

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

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

Двудольный граф является хордальным двудольным тогда и только тогда, когда его матрица смежности полностью уравновешена[en][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.
Источник — https://ru.wikipedia.org/w/index.php?title=Хордальный_двудольный_граф&oldid=135113403