Изменения

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

ГиперграфОбычные графы, у которого арность гиперребрер равна двум( т.е. каждое гиперребро содержит которых ребра могут соединять только две вершины), является графомявляются частным случаем гиперграфа, у которых все гиперребра содержат только две вершины. [[Файл:Hypergraph.jpg|thumb|450px|right|Рис.1Частный случай гипергафа]]     

'''Путем''' (англ. path, смотри также [[Основные_определения_теории_графов#.D0.9F.D1.83.D1.82.D0.B8_.D0.B2_.D0.B3.D1.80.D0.B0.D1.84.D0.B0.D1.85|путь в обычном графе]]) между двумя гиперребрами <tex>e_i</tex> и <tex>e_j</tex> гиперграфа <tex>H</tex> называется последовательность гиперребер <tex>e_{u_1}, e_{u_2} , \ldots ,e_{u_k}</tex>, таких что : 1) # <tex>e_{u_1} = e_i </tex> и <tex>e_{u_k} = e_j</tex> 2) # <tex>\forall v: 1 \leq leqslant v \leq leqslant k-1, e_v \cap e_{v+1} \ne \emptyset</tex>

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

[[Файл:Connected_hypergraph.jpg‎]]рис|thumb|450px|center|Рис.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> называется '''сочленением''' (англ. articulation) <tex>E</tex> , если при его удалении из всех гиперребер <tex>E</tex>, множество разрывается.

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

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

0, & x_i \in e_j \\ 1, & \mathrm{otherwise}

'''Циклом ''' в <tex>H = (X, E)</tex> называется последовательность гиперребер <tex>(e_{i_1}, e_{i_2}, \ldots , e_{i_k})</tex> удовлетворяющим следующим свойствам: 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>

'''Ухом''' (по англ. ear) гиперграфа называется такое гиперребро <tex>e</tex>, что его вершины можно разделить на две группы: 1) # Вершины, которые принадлежат только гиперребру <tex>e</tex> и никакому более. 2) # Вершины, которые принадлежат другим гиперребрам.

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

[[Файл:Acyclic_hyper.png]]рис|thumb|450px|left|Рис.3 Ацикличный гиперграф]]