Хордальный двудольный граф: различия между версиями

По определению хордальные двудольные графы имеют [[Характеризация запрещёнными графами|характеризацию запрещёнными подграфами]] как графы, не содержащие какого-либо [[Порождённый путь|порождённого пути]] длины 3 или длины по меньшей мере 5 (так называемые дыры) в качестве [[Порождённый подграф|порождённого подграфа]]. Таким образом, граф ''G'' является хордальным двудольным тогда и только тогда, когда ''G'' [[Граф без треугольников|не имеет треугольников]] и дыр. ТакжеВ естьстатье две других характеризации<ref>Голамбика{{sfn|Golumbic|1980}}</ref> упоминаются две других характеризации:

''B'' является хордальным двудольным тогда и только тогда, когда любой минимальный [[Рёберныйрёберный сепаратор|рёберный<ref>Рёберный сепаратор — это множество рёбер графа, удаление которых разбивает граф на два не связанных друг с другом подграфа. Обычно при этом накладывается ограничение, что каждый из получившихся подграфов содержит не более 2''N''/3 вершин ([https://www.liquisearch.com/planar_separator_theorem/constructions/edge_separators Planar Separator Theorem - Constructions - Edge Separators]])</ref> порождает полный двудольный подграф в ''B'' и тогда и только тогда, когда любой порождённый подграф является совешенным исключением двудольного графа.

[[Мартин Фарбер]] показал, что граф строго хордален тогда и только тогда, когда двудольный граф инцидентности ([[Граф Леви|граф инцидентности]]) его [[Гиперграфгиперграфа максимальных клик|Гиперграфа<ref>Пусть имеется граф ''G''. Гиперграф на тех же вершинах, гиперрёбрами которого служат максимальные клики графа ''G'' называется гипреграфом максимальных клик]] ({{harv|Gravier, Škrekovski|2001|loc=1}}).</ref> является хордальным двудольным<{{sfn|Farber|1983}}{{sfn|Brandstädt, Le, Spinrad|1999|с=43 Theorem 3.4.1}}.

Аналогичная характеризация имеет место для гиперграфов замкнутых окрестностей — граф сильно хордален тогда и только тогда, когда [[Граф Леви|двудольный граф инцидентности]] его гиперграфа замкнутых окрестностей<ref>Если дан граф <math>G = (V, E)</math>, окрестностью вершины <math>x \in V</math> определяется как <math>N_G(x) = N(x) = \{y \in V| (x,y) \in E\}</math>. Множество <math>N(x)</math> часто называется ''открытой окрестностью'' вершины ''x'', подчёркивая факт, что <math>x \notin V</math> в графе без циклов. Соответственно, множество <math>N_G[x] = N[x] = N(x)\cup\{x\}</math> называется ''замкнутой окрестностью'' вершины ''x''. На вершинах ''V'' можно определить два гиперграфа, положив <math>N(G) = \{N(x)|x \in V\}</math> и <math>N[G] = \{N[x]|x \in V\}</math>. Первый гиперграф называется гиперграфом открытых окрестностей графа ''G''. Второй гиперграф называется гиперграфом замкнутых окрестностей графа ''G'' {{harv|Boros, Gurvich, Zverovich|2006|loc=7, 2.3 Neighborhood hypergraphs}}.</ref> является хордальным двудольным{{sfn|Brandstädt|1991}}.

Другой результат, найденный [[Элиас Далхаус|Элиасом Далхаусом]]: Двудольный граф <math>B = (X,Y,E)</math> является хордальным двудольным тогда и только тогда, когда [[расщепляемый граф]], получающийся из превращения ''X'' в клику, является [[Строго хордальный граф|строго хордальным]]{{sfn|Brandstädt, Le, Spinrad|1999|с=129 Corollary 8.3.2}}.

Двудольный граф ''B''&nbsp;=&nbsp;(''X'',''Y'',''ZE'') является хордальным двудольным тогда и только тогда, когда любой порождённый подграф графа ''B'' имеет упорядочение максимального ''X''-соседства и упорядочение максимального Y- соседства{{sfn|Dragan, Voloshin|1996}}.

Различные результаты описывают связь между хордальными двудольными графами и вполне сбалансированными гиперграфами окрестностей<ref>Цикл <math>(x_1, E_1, \dots, x_p, E_p)</math> гиперграфа <math>H (x_i \in V(H), E_i \in E(H)| i=1,\dots,p)</math> называется ''специальным циклом'' гиперграфа ''H''. Гиперграф называется ''сбалансированным'', если он не содержит специальных циклов нечётной длины. {{harv|Lehel, Tuza|1986|loc=96}}</ref> двудольных графов{{sfn|Brandstädt, Le, Spinrad|1999|с=126–127 Theorems 8.2.5, 8.2.6}}.{{sfn|Huang|2006}}.

Двудольный граф является хордальным двудольным тогда и только тогда, когда его матрица смежности {{не переведено 5|Уравновешенная матрица|полностью уравновешена||balanced matrix}}{{sfn|Farber|1983}}.