Гиперграфы

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

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

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

Рис.1 Частный случай гипергафа

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

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

Путем (англ. 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] 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]H = (X, E)[/math] называется последовательность гиперребер [math](e_{i_1}, e_{i_2}, \ldots , e_{i_k})[/math] удовлетворяющим следующим свойствам: [math]e_{i_k} = e_{i_1}[/math] Для [math]2 \le j \le k - 2[/math] выполняется [math]\forall e \in E : (S_{j-1} \cup S_j \cup S_{j+1}) \setminus e \ne \emptyset [/math], где [math]S_j = e_{i_j} \cap e_{i_{j+1}}[/math] для [math] 1 \le j \le k - 1[/math]

Для определения ацикличного гиперграфа введем определение уха гиперграфа, а также редукцию GYO(Graham-Yu-Ozsoyoglu).

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

Ухом (англ. ear) гиперграфа называется такое гиперребро [math]e[/math], что его вершины можно разделить на две группы: Вершины, которые принадлежат только гиперребру [math]e[/math] и никакому более. Вершины, которые принадлежат другим гиперребрам.

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

Определение редукции GYO (англ. GYO reduction) содержит всего два шага: Устранение вершин, которые содержатся только в одном гиперребре. Удаление гиперребер, которые содержатся в других.

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

Утверждение:

Если гиперграф сводится к пустому с помощью редукции GYO, тогда он ацикличный.

Рис.3 Ацикличный гиперграф

С помощью редукции GYO удаляются вершины A, B и C (т.к они содержатся только в одном своем гиперребре), а затем удаляем оставшиеся внутренние гиперребра.

См. также

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

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

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