Гиперграфы

Определение:

Гиперграфом (англ. hypergraph) [math]H[/math] называют такую пару [math]H = (X, E)[/math] , где [math]X - [/math] множество вершин, а [math]E -[/math] семейство подмножеств [math]X[/math] , называемых гиперребрами (англ. hyperedges)

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

Рис. 1: Гиперграф с множеством вершин [math]V = \{ v_1, v_2, v_3, v_4, v_5, v_6, v_7 \}[/math] и гиперребрами [math]E = \{ \{ v_1, v_2, v_3 \} , \{ v_2, v_3 \} , \{ v_3, v_5, v_6 \} , \{ v_4 \} \}[/math]

Основные понятия гиперграфов

Определение:

Путем (англ. path) между двумя гиперребрами [math]e_i[/math] и [math]e_j[/math] гиперграфа [math]H[/math] называется последовательность гиперребер [math]e_{u_1}, e_{u_2} , \ldots ,e_{u_k}[/math] таких что : [math]e_{u_1} = e_i [/math] и [math]e_{u_k} = e_j[/math] [math]\forall v: 1 \leqslant v \leqslant k-1, e_v \cap e_{v+1} \ne \emptyset[/math]

Определение:

Гиперграф [math]H[/math] называется связным (англ. connected) тогда и только тогда, когда существует путь между каждой парой гиперребер.

Рис. 2: Связный гиперграф

Пусть [math]E - [/math] набор гиперребер, [math]e_1[/math] и [math]e_2 - [/math] элементы [math]E[/math] и [math]q = e_1 \cap e_2[/math].

Определение:

[math]q[/math] называется сочленением (англ. articulation) [math]E[/math] , если при его удалении из всех гиперребер [math]E[/math], множество разрывается.

На рис.2 [math]q = e_4 \cap e_6 = \{ x_{12}, x_{13}\}[/math] является сочленением [math]E[/math].

Матрица инцидентности

Пусть дан гиперграф [math]H = (X, E)[/math] , где [math] X = \{ x_1, x_2, \ldots , x_n \}[/math] и [math] E = \{ e_1, e_2, \ldots , e_m \}[/math]. Любой гиперграф может задаваться матрицей инцидентности (смотри матрицу инцидентности в обычном графе) [math]A = (a_{ij}) [/math] размером [math] n \times m[/math], где

[math] a_{ij} = \left \{ \begin{array}{ll} 0 & x_i \in e_j \\ 1 & \mathrm{otherwise} \end{array} \right. [/math]

Так например, для гиперграфа на рис.1 мы можем построить матрицу инцидентности по таблице отношения принодлежности вершины к гиперребру:

	[math]e_1[/math]	[math]e_2[/math]	[math]e_3[/math]	[math]e_4[/math]
[math]v_1[/math]	✓
[math]v_2[/math]	✓	✓
[math]v_3[/math]	✓	✓	✓
[math]v_4[/math]				✓
[math]v_5[/math]			✓
[math]v_6[/math]			✓
[math]v_7[/math]

[math] A = [/math] [math]\begin{pmatrix} 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ \end{pmatrix}[/math]

Цикл в гиперграфе

Определение:

Простым циклом длины [math]s[/math] в гиперграфе [math]H = (V, E)[/math] называется последовательность [math]( A_0, v_0, A_1, \ldots , A_{s - 1}, v_{s - 1}, A_s)[/math] , где [math]A_0 , \ldots , A_{s - 1} -[/math] различные ребра [math]H[/math] , ребро [math]A_s[/math] совпадает с [math]A_0[/math] , а [math]v_0, \ldots , v_{s - 1} -[/math] различные вершины [math]H[/math] , причем [math]v_i \in A_i \cap A_{i+1}[/math] для всех [math] i = 0, \ldots , s - 1[/math].

Рис. 3: Простейший случай цикла в гиперграфе

Универсальным способом задания гиперграфа является кенигово представление.

Определение:

Кенигово представление гиперграфа [math] H = (V, E) -[/math] обыкновенный двудольный граф [math]K(H)[/math] , отражающий отношение инцидентности различных элементов гиперграфа, с множеством вершин [math]V \cup E [/math] и долями [math]V, E[/math].

Первым, кто дал определение ацикличности гипергафа является Клауд Берж:

Теорема:

Гиперграф [math]H[/math] не содержит циклов в том случае, если его кенигово представление [math]-[/math] ацикличный граф, сожержит в противном случае.

Таким образом, если у нас есть цикл в графе кенигова представления, значит и сам гиперграф имеет цикл.

Рис. 4: Пример гиперграфа, содержащего цикл

Алгоритм нахождения цикла в гиперграфе

Поскольку гиперграф может задаваться кениговым представлением, тогда произведём серию поисков в глубину в двудольном графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе - в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл (если граф неориентированный, то случаи, когда поиск в глубину из какой-то вершины пытается пойти в предка, не считаются).

Ацикличность гиперграфов

Определение:

Редукцией (англ. reduction) гиперграфа [math]H = (V, E)[/math] называется такой гиперграф [math]H' = (V, E')[/math] , который получается из исходного путем удаления всех гиперребер, которые полностью содержатся в других гиперреберах.

Определение:

Гиперграф называется уменьшенным (англ. reduced) , если он эквивалентен своей редукции, то есть не имеет гиперребер внутри других гиперребер.

Пусть [math]M - [/math] множество вершин гиперграфа [math]H = (V, E)[/math]. Множество частичных ребер (англ. partial edges), порожденных множеством [math]M[/math], определяется как множество, полученное путем пересечения гиперребер из множества [math]E[/math] с [math]M[/math]. Таким образом, получаем множество : [math] \{ e \cap M : e \in E \} - \{ \emptyset \} [/math] и берем его редукцию.

Множество частичных ребер, порожденное из гиперграфа [math]H[/math] множеством [math]M[/math], называется вершинно-порожденным (англ. node-generated) множеством частичных ребер.

Определение:

Блоком (англ. block) уменьшенного гиперграфа называется связное, вершинно - порожденное множество частичных ребер без сочленения.

Определение:

Множество частичных ребер называется тривиальным (англ. trivial), если оно содержит одно гиперребро.

Определение:

Уменьшенный гиперграф называется [math] \alpha [/math] - ацикличным (англ. [math] \alpha [/math]-acyclity) , если всего его блоки тривиальны, иначе называют [math] \alpha [/math]-цикличным (англ. [math] \alpha[/math]-cyclity).

Пример

Рис. 5: [math] \alpha[/math]-ацикличный гиперграф

Рис. 6: Подмножество гиперребер [math] \{ ABC, CDE, EFA\} [/math]

Очень просто проверить что на рис. 3 представлен [math] \alpha [/math]-ацикличный гиперграф. Он содержит четыре гиперребра [math]- ABC, CDE, EFA, ACE[/math]. Сочленение для всего множества гиперребер является [math] ABC \cap ACE = AC [/math] , так как после удаления вершин [math]A[/math] и [math]C[/math] гиперграф не будет связным (вершина [math]B[/math] не будет ни с кем соединена). Заметим, что на рис. 6 подмножетсво гиперребер [math]\{ ABC, CDE, EFA \}[/math] не имеет сочленения. Однако, это множество не является вершинно - порожденным , таким образом, нет никаких противоречий с предположением, что гиперграф на рис. 5 является [math] \alpha [/math]-ацикличным.

Заметим, что [math] \alpha [/math]-ацикличность имеет одно нелогичное свойство: при добавлении гиперребер к [math] \alpha [/math]-цикличному гиперграфу он может стать [math] \alpha [/math]-ацикличным (например, при добавлении гиперребра, которое охватывает все вершины, всегда будет делать гиперграф [math] \alpha [/math]-ацикличным). Из-за этого свойства было введено более строгое определение, называемое [math] \beta [/math]-ацикличностью.

Определение:

Гиперграф [math]H = (V, E) [/math] является [math] \beta [/math]-ацикличным (англ. [math] \beta [/math]-acyclity) , если все его подгиперграфы [math] \alpha [/math]-ацикличны.

Так например гиперграф на рис. 5 является [math] \alpha [/math]-ацикличным, но не является [math] \beta [/math]-ацикличным, так как его подгиперграф на рис. 6 является [math] \alpha [/math]-цикличным.

См. также

• Основные определения теории графов

Источники информации

• wikipedia.com — Клауд Берж
• wikipedia.com — Гиперграфы
• sciencedirect.com — Ацикличность в гиперграфах