Гиперграфы

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

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

Гиперграф, у которого арность гиперребрер равна двум( т.е. каждое гиперребро содержит только две вершины), является графом.

Частный случай гипергафа, где [math]E=\{e_1, e_2, e_3, e_4\} = \{\{v_1, v_2, v_3\}, \{v_2,v_3\}, \{v_3,v_5.v_6\}, \{v_4\}\}[/math]

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

Пусть [math]V[/math] - подмножество [math]X[/math]. Множество частичных гиперребер, индуцированных множеством вершин [math]V[/math] в [math]H[/math], называется

[math]E' = \{ e' \mid e' = e \cap V, e \in E \} - \{ \emptyset \}[/math]

[math]E'[/math] называется вершинно-порожденным множеством. С этого момента, будем рассматривать сокращенные гиперграфы(т.е. никакое гиперребро не содержится в другом).

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

Путем между двумя гиперребрами [math]e_i[/math] и [math]e_j[/math] гиперграфа [math]H[/math] называется последовательность гиперребер [math]e_{u_1}, e_{u_2} \ldots e_{u_k},[/math], таких что :

1)[math]e_{u_1} = e_i [/math] и [math]e_{u_k} = e_j[/math]

2)[math]\forall v: 1 \leq v \leq k-1, e_v \cap e_{v+1} \ne \emptyset[/math]

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

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

Пусть [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] называется сочленением [math]E[/math] , если его удаления из всех гиперребер [math]E[/math] разрывает это множество. На рис.1 [math]q = e_4 \cap e_6 = \{ x_{12}, x_{13}\}[/math] является сочленением [math]E[/math].

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

Гиперграф на рис.1 не является [math]\alpha[/math] - ацикличным, так как множество частичных гиперребер [math]\{\{ x_1, x_2, x_3, x_4\}, \{ x_1, x_2, x_5, x_6\}, \{ x_4, x_6, x_8\}\}[/math] является связным, уменьшенным, не тривиальным и не допускают сочленения. Напротив, гиперграф на рис.2 является [math]\alpha[/math] - ацикличным.

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

Пусть дан гиперграф [math]H = (X, E)[/math]. Циклом в [math]H[/math] называется последовательность гиперребер [math](e_{i_1}, e_{i_2}, \ldots , e_{i_k})[/math] удовлетворяющим следующим свойствам:

[math]e_{i_k} = e_{i_1}[/math]

[math]\forall 2 \le j \le k - 2[/math] и [math]\forall e \in E, (S_{j-1} \cup S_j \cup S_{j+1}) \ e \ne \emptyset [/math], где [math]S_j = e_{i_j} \cap e_{i_{j+1}}, \forall 1 \le j \le k - 1[/math]