Гиперграф, у которого арность гиперребрер равна двум( т.е. каждое гиперребро содержит только две вершины), является графом.
[[Файл:Hypergraph.jpg]]рис.1
Частный случай гипергафа, где <tex>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\}\}</tex>
==Основные понятия гиперграфов==
Пусть {{Определение|definition='''Путем''' между двумя гиперребрами <tex>Ve_i</tex> - подмножество и <tex>Xe_j</tex>. Множество '''частичных''' гиперребер, индуцированных множеством вершин гиперграфа <tex>VH</tex> в называется последовательность гиперребер <tex>He_{u_1}, e_{u_2} , \ldots ,e_{u_k}</tex>, называется таких что :
1) <tex>E' = \e_{ e' \mid e' u_1} = e \cap V, e \in E \} - \e_i </tex> и <tex>e_{ \emptyset \u_k}= e_j</tex>
2) <tex>E'\forall v: 1 \leq v \leq k-1, e_v \cap e_{v+1} \ne \emptyset</tex> называется '''вершинно-порожденным''' множеством. С этого момента, будем рассматривать сокращенные гиперграфы(т.е. никакое гиперребро не содержится в другом).}}
Рассмотрим множество {{Определение|definition=Гиперграф <tex>H</tex> называется '''связным''' тогда и только тогда, когда существует путь между каждой парой гиперребер.}} [[Файл:Connected_hypergraph.jpg]]рис.2 Связный гиперграф Пусть <tex>E</tex> - связный, сокращенный набор гиперребер, <tex>e_1</tex> и <tex>e_2</tex> - элементы <tex>E</tex> и <tex> V q = e_1 \subset Xcap e_2</tex>. {{Определение|definition=<tex>q</tex> называется '''Подгиперграфомсочленением''' гиперграфа <tex>HE</tex>, индуцированного множеством вершин если при его удалении из всех гиперребер <tex>VE</tex>, наызывается такой множество разрывается.}} На рис.2 <tex>q = e_4 \cap e_6 = \{ x_{12}, x_{13}\}</tex> является сочленением <tex>E</tex>. ==Матрица инцидентности == Пусть дан гиперграф <tex>H[V] = (VX, E')</tex> с множеством гиперребер , где <tex>E'X = \{ x_1, x_2, \ldots , x_n \}</tex>и <tex> E = \{ e_1, которое является множеством частичных гиперреберe_2, \ldots , индуцированных множеством вершин e_m \}</tex>V. Любой гиперграф может задаваться матрицей инцидентности <tex>A = (a_{ij}) </tex> в размером <tex>Hn \times m</tex>., где
'''Путем''' между двумя гиперребрами <tex>e_i</tex> и <tex>e_j</tex> гиперграфа <tex>H</tex> называется последовательность гиперребер <tex>e_a_{ij} = \left \{ \begin{u_1array}, e_{u_2ll} 0, & x_i \ldots e_in e_j \\ 1, & otherwise \end{u_karray}, \right.</tex>, таких что :
Так например, для гиперграфа на рис.1)<tex>e_{u_1} = e_i </tex> и <tex>e_{u_k} = e_j</tex>мы имеем такую матрицу инцидентности
2)<tex>\forall v: 1 \leq v \leq k-1, e_v \cap e_{v+1} \ne \emptyset</tex>
[[Файл<tex> A = </tex><tex>\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}</tex> ==Ацикличность гиперграфа== {{Определение|definition=Циклом в <tex>H = (X, E)</tex> называется последовательность гиперребер <tex>(e_{i_1}, e_{i_2}, \ldots , e_{i_k})</tex> удовлетворяющим следующим свойствам:Connected_hypergraph 1) <tex>e_{i_k} = e_{i_1}</tex> 2) <tex>\forall 2 \le j \le k - 2</tex> выполняется <tex>\forall e \in E : (S_{j-1} \cup S_j \cup S_{j+1}) \setminus e \ne \emptyset </tex>, где <tex>S_j = e_{i_j} \cap e_{i_{j+1}}</tex> для которых выполняется <tex>\forall 1 \le j \le k - 1</tex>}} Для определения ацикличного гиперграфа введем определение '''уха''' гиперграфа, а также редукцию GYO(Graham-Yu-Ozsoyoglu).jpg]]рис{{Определение|definition=Ухом(по англ.1 Связный гиперграфear) гиперграфа называется такое гиперребро <tex>e</tex>, что его вершины можно разделить на две группы:
1) Вершины, которые принадлежат только гиперребру <tex>e</tex> и никакому более.
Гиперграф <tex>H</tex> называется '''связным''' тогда и только тогда2) Вершины, когда существует путь между каждой парой гиперреберкоторые принадлежат другим гиперребрам.}}
Пусть <tex>E</tex> - связный, сокращенный набор гиперребер, <tex>e_1</tex> и <tex>e_2</tex> - элементы <tex>E</tex> и <tex>q = e_1 \cap e_2</tex>. <tex>q</tex> называется '''сочленением''' <tex>E</tex> , если его удаления из всех гиперребер <tex>E</tex> разрывает это множество. На рис.1 <tex>q = e_4 \cap e_6 = \{ x_{12}, x_{13}\}</tex> является сочленением <tex>E</tex>.Определение|definition=Определение редукции GYO содержит всего два шага:
Гиперграф называется <tex>\alpha</tex> - ацикличным, если каждое множество частичных ребер является связными, сокращенным, индуцированным множеством 1) Устранение вершин и не допускающее сочленения, является тривиальным(т.е. содержит которые содержатся только один элемент)в одном гиперребре.
Гиперграф на рис.1 не является <tex>\alpha</tex> - ацикличным, так как множество частичных 2) Удаление гиперребер <tex>\{\{ x_1, x_2, x_3, x_4\}, \{ x_1, x_2, x_5, x_6\}, \{ x_4, x_6, x_8\которые содержатся в других.}\}</tex> является связным, уменьшенным, не тривиальным и не допускают сочленения. Напротив, гиперграф на рис.2 является <tex>\alpha</tex> - ацикличным.
[[Файл:AcyclicТо есть, мы удаляем вершины которые содержатся в ухе, и ни в каком более гиперребре.jpg]]рисЗатем удаляем гиперребра, оставляя другие вершины.2 <tex>\alpha</tex> - ацикличный гиперграф
Пусть дан {{Утверждение|statement=Если гиперграф <tex>H = (Xсводится к пустому с помощью редукции GYO, E)</tex>тогда он ацикличный. Циклом в <tex>H</tex> называется последовательность гиперребер <tex>(e_{i_1}, e_{i_2}, \ldots , e_{i_k})</tex> удовлетворяющим следующим свойствам:
<tex>e_{i_k} = e_{i_1}</tex>[[Файл:Acyclic_hyper.png]]рис.3 Ацикличный гиперграф
<tex>\forall 2 \le j \le k - 2</tex> С помощью редукции GYO удаляются вершины A, B и <tex>\forall e \in E, C (S_{j-1} \cup S_j \cup S_{j+1}т.к они содержатся только в одном своем гиперребре) \ e \ne \emptyset </tex>, где <tex>S_j = e_{i_j} \cap e_{i_{j+1}}, \forall 1 \le j \le k - 1</tex>а затем удаляем оставшиеся внутренние гиперребра.
