Изменения

В математике '''гиперграф''' - это обобщение графа, у которого ребра могут соединять любое количество вершин. Более формально, гиперграф {{Определение|definition=Гиперграфом <tex>H</tex> - это пара называют такую пару <tex>H = (X, E)</tex> , где <tex>X</tex> - множество элементов называемых узлами или вершинамивершин, и а <tex>E</tex> - не пустое подмножество <tex>семейство подмножеств X</tex> , называемых '''гиперребрами или просто ребрами.''' }}

В то время, как ребра графа соединяют две пары вершин, гиперребра - произвольные множества вершин, которые могут содержать любое количество вершин. Однако, очень часто рассматривают гиперграфы с гиперребрами одинаковой мощности ; <tex>k</tex> - равномерный гиперграф - это такой гиперграфГиперграф, у которого все гиперребра имеют размер kарность гиперребрер равна двум( т. (Другими словами, такой гиперграф множество подмножеств, которые содержат k вершине. каждое гиперребро содержит только две вершины). Так например, <tex>2</tex> - равномерный гиперграф - обычный графявляется графом.

[[Файл:Hypergraph.jpg|right|thumb|]]Частный случай гипергафа, где <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>]]Стоит заметить, что обычный граф является частным случаем гиперграфа, где каждое ребро имеет мощность <tex>2</tex>.

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

Так как множество гиперребер может быть любой мощности, существуют несколько понятий '''подграфа''' гиперграфа, называемых '''подгиперграфами''', '''частичные гиперграфы''' и '''разрез гиперграфов'''. Пусть <tex>H = (X, E) V</tex> - гиперграф содержащий множество вершин подмножество <tex>X = \{x_i | i \in I_v\}</tex> и множество ребер <tex>E = \{e_i | i \in I_e. Множество '''частичных''' гиперребер, e_i \subseteq X\}индуцированных множеством вершин </tex>, где <tex>I_vV</tex> и в <tex>I_eH</tex> множества индексов вершин и ребер соответсвенно.
, называется

'''Подгиперграфом''' называют гиперграф с некоторым множеством удаленных вершин. Формально, подгиперграф <tex>H_a</tex> , индуцированный подмножеством <tex>A</tex> множества <tex> X </tex>, который определен как 
<tex>H_a E' = (A, \{e_i e' \mid e' = e \cap A| e_i V, e \cap A in E \} - \neq { \emptyset \}).</tex>

<tex>E'</tex> называется '''Частичнымвершинно-порожденным''' гипергафом называется гиперграф, с множеством удаленных ребер. Данное подмножество <tex>J \subset I_e </tex> множества индексов ребер, частичный граф сгенерирован с помощью <tex>J</tex>С этого момента, будем рассматривать сокращенные гиперграфы(т.е <tex>(X, \{ e_i | i \in J \}. никакое гиперребро не содержится в другом).</tex>

Пусть дано Рассмотрим множество <tex>A V \subseteq subset X</tex>, разрезом гиперграфа называют такой . '''частичныйПодгиперграфом''' гиперграфа <tex>H</tex>, индуцированного множеством вершин <tex>V</tex>, наызывается такой гиперграф <tex>
H \times A H[V] = (AV, \{e_i | i \in I_eE')</tex> с множеством гиперребер <tex>E'</tex>, которое является множеством частичных гиперребер, e_i \subseteq A \}).индуцированных множеством вершин <tex>V</tex> в <tex>H</tex>.

'''ДвойственнымПутем''' гиперграфом между двумя гиперребрами <tex>He_i</tex>* к и <tex>He_j</tex> называют такой гиперграф, в котором поменяны местами вершины и ребра таким образом, что вершины определяются как гиперграфа <tex>\{e_i\}H</tex> и ребра определяются как называется последовательность гиперребер <tex>\e_{X_m\u_1}</tex>, где <tex>X_m = e_{u_2} \ldots e_{ e_i | x_m \in e_i \u_k}.,</tex>, таких что :

Когда операция равенства определена, как показано ниже, операция взятия '''двойственного''' гиперграфа выглядит следующим образом
1)<tex>(H^*)^* e_{u_1} = e_i </tex> и <tex>e_{u_k} = H.e_j</tex>

Связный граф 2)<tex>G</tex> с тем же множеством вершин\forall v: 1 \leq v \leq k-1, что и у связного гиперграфа <tex>H</tex> называется «принимающим» графом для <tex>H</tex>, если каждое гиперребро <tex>H</tex> включает связный подграф в <tex>G</tex>. Для несвязного гиперграфа <tex>H</tex> , <tex>G</tex> является «принимающим», если существует биекция между связными компонентами <tex>G</tex> и <tex>H</tex> , так что каждая связная компонента <tex>G</tex>' графа <tex>G</tex> является принимающей для соответствующего <tex>He_v \cap e_{v+1} \ne \emptyset</tex>'.

==Изоморфность и эквивалентность==Гиперграф <tex>H = (X, E)</tex> изоморфен гиперграфу <tex>G = (Y, F)</tex> , записывается как <tex>H \simeq G</tex>, если существует биекция <tex>w</tex> [[Файл: <tex>X</tex> -> <tex>Y</tex>
 и перестановка <tex>\pi</tex> множества <tex>I</tex> такая, что <tex>w</tex><tex>(e_i)</tex> = <tex>f_{\pi(i)}</tex>Connected_hypergraph.jpg‎]]Тогда биекция <tex>w</tex> называется изоморфизмом гиперграфоврис. Стоит отметить, что <tex>H \simeq G</tex> тогда и только тогда, когда <tex>H^* \simeq G^*</tex>1 Связный гиперграф

Когда вершины гиперграфа явно помечены, то появляется понятие '''эквивалентности''', а также '''равенства'''. Говорят, что Гиперграф <tex>H</tex> эквивалентен <tex>G</tex>называется '''связным''' тогда и только тогда, записывается как <tex>H \equiv G</tex>, если изоморфизм <tex>w</tex> имеет следующие свойства когда существует путь между каждой парой гиперребер.

Пусть <tex>w(x_n) E</tex> - связный, сокращенный набор гиперребер, <tex>e_1</tex> и <tex>e_2</tex> - элементы <tex>E</tex> и <tex>q = y_ne_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>.

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

Гиперграф на рис.1 не является <tex>w(e_i) = f_\alpha</tex> - ацикличным, так как множество частичных гиперребер <tex>\{\{x_1, x_2, x_3, x_4\pi(i)}, \{ x_1, x_2, x_5, x_6\}, \{ x_4, x_6, x_8\}\}</tex> является связным, уменьшенным, не тривиальным и не допускают сочленения. Напротив, гиперграф на рис.2 является <tex>\alpha</tex>- ацикличным.

Заметим, что <tex>H \equiv G</tex> если, и только если <tex>H^* \cong G^*</tex>[[Файл:Acyclic.jpg]]Если, кроме того, перестановка рис.2 <tex>\pi</tex> тождественна, то говорят, что <tex>Halpha</tex> равен <tex>G</tex>, и записывается как <tex>H = G</tex>. Стоит отметить, что при таком определении равенства, графы самодвойственны, т.е. <tex>(H^*)^* = H</tex>.- ацикличный гиперграф

'''Автоморфизмом''' гиперграфа Пусть дан гиперграф <tex>H = (X, E)</tex>. Циклом в <tex>H</tex> называется изоморфизм из множества вершин в них жепоследовательность гиперребер <tex>(e_{i_1}, e_{i_2}, \ldots , т.е. переобозначение вершин.e_{i_k})</tex> удовлетворяющим следующим свойствам:

Рассмотрим гиперграфы с ребрами   <tex>H = \{ e_1 = \{ a, b \}, e_2 = \{ b, c\}, e_3 = \{ c, d \}, e_4 = \{d, a\}, e_5 = \{b, d \}, e_6 = \{a, c \}\}</tex>  <tex>G = \{ f_1 = \{\alpha, \beta\}, f_2 = \{\beta,\gamma\}, f_3 = \{\gamma,\delta\}, f_4 = \{\delta,\alpha\},f_5=\{\alpha,\gamma\},f_6=\{\beta,\delta\}\}</tex>  Тогда, очевидно, <tex>H</tex> и <tex>G</tex> изоморфны(с <tex>w(a) = \alpha</tex>, и т.д.), но они не строго изоморфны. Так, например, в <tex>H</tex> вершина <tex>a</tex> содержится в ребрах forall <tex>1, 4</tex> и <tex>6</tex>, так что  <tex> e_1 2 \cap e_4 le j \cap e_6 = \{a\}</tex> Однако в <tex>G</tex> не существует вершины, которая содержится в ребрах <tex> 1, 4</tex> и <tex>6</tex>: <tex> f_1 \cap f_4 \cap f_6 = \emptyset </tex> В этом примере <tex>H</tex> и <tex>G</tex> эквивалентны, <tex>H \equiv G</tex>, и двойственные строго изоморфны: <tex>H^* \cong G^*</tex>. ==Ацикличность== В отличие от обычных неориентированных графов, для которых существует только одно понятие ацикличности, существует множество неэквивалентных определений ацикличности гиперграфов. Первое определение ацикличности для гиперграфов было дано Клаудом Бержем: гиперграф называется ацикличным по Бержу, если инцидентный ему граф ацикличный. Это определение достаточно ограничено. Например, если гиперграф имеет какуюle k -то пару вершин <tex>v \ne v'2</tex> и какую-то пару гиперребер <tex>f \ne f'</tex>, таких что <tex>v, v' forall e \in f</tex> и <tex>v, v' \in f'</tex>, тогда имеет место цикл по Бержу. Цикличность по Бержу может быть найдена за линейное время с помощью исследования инцидентности гиперграфа. Также мы можем определить более слабое определение ацикличности гиперграфа, называемое <tex>\alpha</tex> - ацикличность. Это понятие ацикличности эквивалентно определению гиперграфаE, который является конформальным(т.е. каждая клика исходного графа покрыта какимS_{j-то гиперребром), и при этом исходный граф является хордальным ; это также эквивалентно сводимости пустого графа через GYO алгоритм(более известный как алгоритм Грэхема), повторяющийся процесс, который удаляет гиперребра с использованием главного определения "ухо графа". В области теории баз данных известно, что схема баз данных обладает некоторыми желательными свойствами, если ее основной граф является <tex>\alpha</tex> - ациклическим. <tex>\alpha</tex> - ацикличность гиперграфа также может быть найдена за линейное время.  Стоит отметить, что <tex>\alpha</tex> - ацикличность графа имеет некоторое нелогичное свойство, а именно, что при добавлении к <tex>\alpha</tex> - цикличному графу гиперребер гиперграф может стать <tex>\alpha</tex> - ацикличным. Например, добавление гиперребра, которое содержит все вершина гиперграфа, всегда будет давать <tex>\alpha</tex> - ацикличность графа. Частично мотивированным этим недостатком, Рональд Феджин определил более сильные понятия - <tex>\beta</tex> - ацикличность и <tex>\gamma</tex> - ацикличность. Можно констатировать <tex>\beta</tex> - ацикличность как требование, чтобы все подгиперграфы исходного гиперграфа были <tex>\alpha</tex> - ацикличными, что ээквивалентно выше упомянотому определению Грэхема. Понятие <tex>1} \gamma</tex> - ацикличности имеет более ограниченное определение, которое эквивалентно несколькими желательными свойствами схем баз данных и связана с диаграммами Бахмена. <tex<\beta</tex> - ацикличность и <tex>\gamma</tex> - ацикличность может быть найдена за полиномиальное время. ==Матрица инцидентности== Пусть <tex>V = cup S_j \cup S_{ v_1, v_2, ... , v_n \j+1},</tex> и <tex>E = ) \{ e_1, e_2, ..., e_m e \}</tex>. Каждый гиперграф имеет <tex>n ne \times m</tex> инцидентную матрицу <tex>A = (a_{ij}) emptyset </tex>, где  <tex> a_S_j = e_{iji_j} = \left \cap e_{ \begini_{arrayj+1}{ll} 1,& v_i \in e_j \\ 0,& otherwiseforall 1 \end{array} le j \right.</tex> Транспонированная матрица  <tex>A^t</tex> инцидентной матрицы определяет гиперграф <tex>H^* = (V^*, E^*)</tex> называемая двойственной к <tex>H</tex> , где <tex>V^*</tex> явялется <tex>m</tex>le k -ым элементом множества и <tex>E^*</tex> является <tex>n</tex>-ым элементом множества подмножества <tex>V^*</tex>. Для <tex>v^*_j \in V^*</tex> и <tex>e^*_i \in E^*, v^*_j \in e^*_i</tex> если, и только если <tex>a_{ij} = 1</tex>. ==Симметричные гиперграфы== '''Рангом''' <tex>r(H)</tex> гиперграфа <tex>H</tex> называется максимальная мощность любого из гиперребер в гиперграфе. Если все ребра имеют одинаковыую мощность <tex>k</tex> , тогда гиперграф называется однородным или <tex>k</tex> - однородным, или <tex>k</tex> - гиперграфом. Обычный граф является 2-однородным гиепрграфом. Степенью <tex>d(v)</tex> вершины <tex>v</tex> называется число гиперребер, которые содержат <tex>v</tex>. <tex>H</tex> называется'''<tex>k</tex>- регулярным''', если каждая вершина имеет степень <tex>k</tex>. Две вершины <tex>x</tex> и <tex>y</tex> гиперграфа <tex>H</tex> называются симметричными, если существует такой автоморфизм, что <tex>w(x) = y</tex>. Тва ребра <tex>e_i</tex> и <tex>e_j</tex> называются симметричными, если существет такой автоморфизм, что <tex>w(e_i) = e_j</tex>. Гиперграф называется '''вершинно-транзитивным'''(или '''вершинно-симметричным'''), если все вершины симметричны. Точно так же, гиперграф называется '''реберно-транзитивным'''6 если все его ребра симметричны. Если гиперграф и вершинно-тразитивный, и реберно-транзитивный , тогда гиперграф называется '''транзитивным'''.