Гиперграфы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(sta)
м (rollbackEdits.php mass rollback)
 
(не показано 14 промежуточных версий 3 участников)
Строка 1: Строка 1:
В математике '''гиперграф''' - это обобщение графа, у которого ребра могут соединять любое количество вершин. Более формально, гиперграф <tex>H</tex> - это пара <tex>(X, E)</tex> , где <tex>X</tex> - множество элементов называемых узлами или вершинами, и <tex>E</tex> - не пустое подмножество <tex>X</tex> называемых гиперребрами или просто ребрами.
+
{{Определение
 +
|definition=
 +
'''Гиперграфом''' (англ. ''hypergraph'') <tex>H</tex> называют такую пару <tex>H = (X, E)</tex> , где <tex>X - </tex> множество вершин, а <tex>E -</tex> семейство подмножеств <tex>X</tex> , называемых '''гиперребрами''' (англ. ''hyperedges'')
 +
}}
  
В то время, как ребра графа соединяют две пары вершин, гиперребра - произвольные множества вершин, которые могут содержать любое количество вершин. Однако, очень часто рассматривают гиперграфы с гиперребрами одинаковой мощности ; <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>]]
+
[[Файл:Hypergraph.jpg|thumb|450px|Рис. 1: Гиперграф с множеством вершин <tex>V = \{ v_1, v_2, v_3, v_4, v_5, v_6, v_7 \}</tex> и гиперребрами <tex>E = \{ \{ 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) </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_v</tex> и <tex>I_e</tex> множества индексов вершин и ребер соответсвенно.

 
  
'''Подгиперграфом''' называют гиперграф с некоторым множеством удаленных вершин. Формально, подгиперграф <tex>H_a</tex> , индуцированный подмножеством <tex>A</tex> множества <tex> X </tex>, который определен как 
<tex>H_a = (A, \{e_i \cap A| e_i \cap A  \neq \emptyset \}).</tex>
+
==Основные понятия гиперграфов==
  
'''Частичным''' гипергафом называется гиперграф, с множеством удаленных ребер. Данное подмножество <tex>J \subset I_e </tex> множества индексов ребер, частичный граф сгенерирован с помощью <tex>J</tex>, т.е <tex>(X, \{ e_i | i \in J \}).</tex>
+
{{Определение
 +
|definition=
 +
'''Путем''' (англ. ''path'') между двумя гиперребрами <tex>e_i</tex> и <tex>e_j</tex> гиперграфа <tex>H</tex> называется последовательность гиперребер <tex>e_{u_1}, e_{u_2} , \ldots  ,e_{u_k}</tex> таких что :
 +
# <tex>e_{u_1} = e_i </tex> и <tex>e_{u_k} = e_j</tex>
 +
# <tex>\forall v: 1 \leqslant v \leqslant k-1, e_v \cap e_{v+1} \ne \emptyset</tex>
 +
}}
  
Пусть дано множество <tex>A \subseteq X</tex>, разрезом гиперграфа называют такой '''частичный''' гиперграф <tex>
H \times A = (A, \{e_i | i \in I_e, e_i \subseteq A \}).</tex>
+
{{Определение
 +
|definition=
 +
Гиперграф <tex>H</tex> называется '''связным''' (англ. ''connected'') тогда и только тогда, когда существует путь между каждой парой гиперребер.
 +
}}
  
'''Двойственным''' гиперграфом <tex>H</tex>* к <tex>H</tex> называют такой гиперграф, в котором поменяны местами вершины и ребра таким образом, что вершины определяются как <tex>\{e_i\}</tex> и ребра определяются как <tex>\{X_m\}</tex>, где <tex>X_m = \{ e_i | x_m \in e_i \}.</tex>
+
[[Файл:Connected_hypergraph.jpg‎|thumb|450px|center|Рис. 2: Связный гиперграф]]
  
Когда операция равенства определена, как показано ниже, операция взятия '''двойственного''' гиперграфа выглядит следующим образом
<tex>(H^*)^* = H.</tex>
+
Пусть <tex>E - </tex> набор гиперребер, <tex>e_1</tex> и <tex>e_2 - </tex> элементы <tex>E</tex> и <tex>q = e_1 \cap e_2</tex>.
 +
{{Определение
 +
|definition=
 +
<tex>q</tex> называется '''сочленением''' (англ. ''articulation'') <tex>E</tex> , если при его удалении из всех гиперребер <tex>E</tex>, множество разрывается.
 +
}}
  
Связный граф <tex>G</tex> с тем же множеством вершин, что и у связного гиперграфа <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>H</tex>'.
+
На рис.2 <tex>q = e_4 \cap e_6 = \{ x_{12}, x_{13}\}</tex> является сочленением <tex>E</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>
 
Тогда биекция <tex>w</tex> называется изоморфизмом гиперграфов. Стоит отметить, что
 
<tex>H \simeq G</tex> тогда и только тогда, когда <tex>H^* \simeq G^*</tex>
 
  
Когда ребра гиперграфа явно помечены, то появляется дополнительное понятие '''сильного изоморфизима'''. Говорят, что <tex>H</tex> '''сильно изоморфен''' <tex>G</tex> , если перестановка является тождественной. Записывается как <tex>H \cong G</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>, где
  
Когда вершины гиперграфа явно помечены, то появляется понятие '''эквивалентности''', а также  '''равенства'''. Говорят, что <tex>H</tex> эквивалентен <tex>G</tex>, записывается как <tex>H \equiv G</tex>, если изоморфизм <tex>w</tex> имеет следующие свойства
+
<tex> a_{ij} = \left \{
 +
\begin{array}{ll}
 +
0 & x_i \in e_j \\
 +
1 & \mathrm{otherwise}
 +
\end{array}
 +
\right.
 +
</tex>
  
<tex>w(x_n) = y_n</tex>
+
Так например, для гиперграфа на рис.1 мы можем построить матрицу инцидентности по таблице отношения принодлежности вершины к гиперребру:
  
и
+
{| class="wikitable" align="left" style="color: black; background-color:#ffffcc;" cellpadding="10"
 +
|+
 +
!
 +
!<tex>e_1</tex>
 +
!<tex>e_2</tex>
 +
!<tex>e_3</tex>
 +
!<tex>e_4</tex>
 +
|-align="center"
 +
!<tex>v_1</tex>
 +
|✓|||| ||
 +
|-align="center"
 +
!<tex>v_2</tex>
 +
|✓||✓|| ||
 +
|-align="center"
 +
!<tex>v_3</tex>
 +
|✓||✓||✓||
 +
|-align="center"
 +
!<tex>v_4</tex>
 +
| |||| ||✓
 +
|-align="center"
 +
!<tex>v_5</tex>
 +
|||||✓||
 +
|-align="center"
 +
!<tex>v_6</tex>
 +
|||||✓||
 +
|-align="center"
 +
!<tex>v_7</tex>
 +
|||||||
 +
|}
  
<tex>w(e_i) = f_{\pi(i)}</tex>
 
  
Заметим, что <tex>H \equiv G</tex> если, и только если <tex>H^* \cong G^*</tex>.
+
<tex> A = </tex>
Если, кроме того, перестановка <tex>\pi</tex> тождественна, то говорят, что <tex>H</tex> равен <tex>G</tex>, и записывается как <tex>H = G</tex>. Стоит отметить, что при таком определении равенства, графы самодвойственны, т.е. <tex>(H^*)^* = H</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>
  
'''Автоморфизмом''' гиперграфа называется изоморфизм из множества вершин в них же, т.е. переобозначение вершин.
 
  
Пример.
 
  
Рассмотрим гиперграфы с ребрами
 
  
  
<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>
+
==Цикл в гиперграфе==
  
 +
{{Определение
 +
|definition=
 +
'''Простым циклом''' длины <tex>s</tex> в гиперграфе <tex>H = (V, E)</tex> называется последовательность <tex>( A_0, v_0, A_1, \ldots , A_{s - 1}, v_{s - 1}, A_s)</tex> , где <tex>A_0 , \ldots , A_{s - 1} -</tex> различные ребра <tex>H</tex> , ребро <tex>A_s</tex> совпадает с  <tex>A_0</tex> , а <tex>v_0, \ldots , v_{s - 1} -</tex> различные вершины <tex>H</tex> , причем <tex>v_i \in A_i \cap A_{i+1}</tex> для всех <tex> i = 0, \ldots , s - 1</tex>. 
 +
}}
  
Тогда, очевидно, <tex>H</tex> и <tex>G</tex> изоморфны(с <tex>w(a) = \alpha</tex>, и т.д.), но они не строго изоморфны. Так, например, в <tex>H</tex> вершина <tex>a</tex> содержится в ребрах  <tex>1, 4</tex> и <tex>6</tex>, так что
+
[[Файл:Cycle_hyper.jpg|thumb|450px|center|Рис. 3: Простейший случай цикла в гиперграфе]]
  
<tex> e_1 \cap e_4 \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>
+
{{Определение
 +
|definition=
 +
'''Кенигово представление''' гиперграфа <tex> H = (V, E) -</tex> обыкновенный двудольный граф '''<tex>K(H)</tex>''' , отражающий отношение инцидентности различных элементов гиперграфа, с множеством вершин <tex>V \cup E </tex> и долями <tex>V, E</tex>.
 +
}}
  
В этом примере <tex>H</tex> и <tex>G</tex> эквивалентны, <tex>H \equiv G</tex>, и двойственные строго изоморфны: <tex>H^* \cong G^*</tex>.
+
Первым, кто дал определение ацикличности гипергафа является Клауд Берж:
  
 +
{{Теорема
 +
|statement=
 +
Гиперграф <tex>H</tex> не содержит циклов в том случае, если его кенигово представление <tex>-</tex> ацикличный граф, сожержит в противном случае.
 +
}}
  
==Ацикличность==
+
Таким образом, если у нас есть цикл в графе кенигова представления, значит и сам гиперграф имеет цикл.
  
В отличие от обычных неориентированных графов, для которых существует только одно понятие ацикличности, существует множество неэквивалентных определений ацикличности гиперграфов.
+
[[Файл:Cycle_example.png|thumb|center|500px|Рис. 4: Пример гиперграфа, содержащего цикл]]
  
Первое определение ацикличности для гиперграфов было дано Клаудом Бержем: гиперграф называется ацикличным по Бержу, если инцидентный ему граф ацикличный. Это определение достаточно ограничено. Например, если гиперграф имеет какую-то пару вершин <tex>v \ne v'</tex> и какую-то пару гиперребер <tex>f \ne f'</tex>, таких что <tex>v, v' \in f</tex> и <tex>v, v' \in f'</tex>, тогда имеет место цикл по Бержу. Цикличность по Бержу может быть найдена за линейное время с помощью исследования инцидентности гиперграфа.
+
===Алгоритм нахождения цикла в гиперграфе===
  
Также мы можем определить более слабое определение ацикличности гиперграфа, называемое <tex>\alpha</tex> - ацикличность. Это понятие ацикличности эквивалентно определению гиперграфа, который является конформальным(т.е. каждая клика исходного графа покрыта каким-то гиперребром), и при этом исходный граф является хордальным ; это также эквивалентно сводимости пустого графа через 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>\gamma</tex> - ацикличности имеет более ограниченное определение, которое эквивалентно несколькими желательными свойствами схем баз данных и связана с диаграммами Бахмена. <tex<\beta</tex> - ацикличность и <tex>\gamma</tex> - ацикличность может быть найдена за полиномиальное время.
+
==Ацикличность гиперграфов==
  
==Матрица инцидентности==
+
{{Определение
 +
|definition=
 +
'''Редукцией''' (англ. ''reduction'') гиперграфа <tex>H = (V, E)</tex> называется такой гиперграф <tex>H' = (V, E')</tex> , который получается из исходного путем удаления всех гиперребер, которые полностью содержатся в других гиперреберах.
 +
}}
  
Пусть <tex>V = \{ v_1, v_2, ... , v_n \},</tex> и <tex>E = \{ e_1, e_2, ..., e_m \}</tex>. Каждый гиперграф имеет <tex>n \times m</tex> инцидентную матрицу <tex>A = (a_{ij}) </tex>, где
+
{{Определение
 +
|definition=
 +
Гиперграф называется '''уменьшенным''' (англ. ''reduced'') , если он эквивалентен своей редукции, то есть не имеет гиперребер внутри других гиперребер.
 +
}}
 +
 
 +
Пусть <tex>M - </tex> множество вершин гиперграфа <tex>H = (V, E)</tex>. Множество '''частичных ребер''' (англ. ''partial edges''), порожденных множеством <tex>M</tex>, определяется как множество, полученное путем пересечения гиперребер из множества <tex>E</tex> с <tex>M</tex>. Таким образом, получаем множество : <tex> \{ e \cap M : e \in E \} - \{ \emptyset \} </tex> и берем его редукцию.
 +
 
 +
Множество частичных ребер, порожденное из гиперграфа <tex>H</tex> множеством <tex>M</tex>, называется '''вершинно-порожденным''' (англ. ''node-generated'') множеством частичных ребер.
 +
 
 +
{{Определение
 +
|definition=
 +
'''Блоком''' (англ. ''block'') уменьшенного гиперграфа называется связное, вершинно - порожденное множество частичных ребер без сочленения.
 +
}}
 +
 
 +
{{Определение
 +
|definition=
 +
Множество частичных ребер называется '''тривиальным''' (англ. ''trivial''), если оно содержит одно гиперребро.
 +
}}
 +
 
 +
{{Определение
 +
|definition=
 +
Уменьшенный гиперграф называется '''<tex> \alpha </tex> - ацикличным''' (англ. ''<tex> \alpha </tex>-acyclity'') , если всего его блоки тривиальны, иначе называют '''<tex> \alpha </tex>-цикличным''' (англ. ''<tex> \alpha</tex>-cyclity'').
 +
}}
 +
 
 +
''Пример''
 +
 
 +
[[Файл:Alpha-acyclity-1.png|thumb|left|500px|Рис. 5: <tex> \alpha</tex>-ацикличный гиперграф]]
 +
[[Файл:Alpha-acyclity-2.png|thumb|center|500px|Рис. 6:  Подмножество гиперребер <tex> \{ ABC, CDE, EFA\} </tex>]]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
Очень просто проверить что на рис. 3 представлен <tex> \alpha </tex>-ацикличный гиперграф. Он содержит четыре гиперребра <tex>- ABC, CDE, EFA, ACE</tex>. Сочленение для всего множества гиперребер является <tex> ABC \cap ACE = AC </tex> , так как после удаления вершин <tex>A</tex> и <tex>C</tex> гиперграф не будет связным (вершина <tex>B</tex> не будет ни с кем соединена). Заметим, что на рис. 6 подмножетсво гиперребер <tex>\{ ABC, CDE, EFA \}</tex> не имеет сочленения. Однако, это множество не является вершинно - порожденным , таким образом, нет никаких противоречий с предположением, что гиперграф на рис. 5 является <tex> \alpha </tex>-ацикличным.
  
<tex> a_{ij} = \left \{
 
\begin{array}{ll}
 
1,& v_i \in e_j \\
 
0,& otherwise
 
\end{array}
 
\right.
 
</tex>
 
  
Транспонированная матрица  <tex>A^t</tex> инцидентной матрицы определяет гиперграф <tex>H^* = (V^*, E^*)</tex> называемая двойственной к <tex>H</tex> , где <tex>V^*</tex> явялется <tex>m</tex>-ым элементом множества и <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> \alpha </tex>-ацикличность имеет одно нелогичное свойство: при добавлении гиперребер к <tex> \alpha </tex>-цикличному гиперграфу он может стать <tex> \alpha </tex>-ацикличным (например, при добавлении гиперребра, которое охватывает все вершины, всегда будет делать гиперграф <tex> \alpha </tex>-ацикличным). Из-за этого свойства было введено более строгое определение, называемое <tex> \beta </tex>-ацикличностью.
  
==Симметричные гиепрграфы==
+
{{Определение
 +
|definition=
 +
Гиперграф <tex>H = (V, E) </tex> является '''<tex> \beta </tex>-ацикличным''' (англ. ''<tex> \beta </tex>-acyclity'') , если все его подгиперграфы <tex> \alpha </tex>-ацикличны.
 +
}}
  
'''Рангом''' <tex>r(H)</tex> гиперграфа <tex>H</tex> называется максимальная мощность любого из гиперребер в гиперграфе. Если все ребра имеют одинаковыую мощность <tex>k</tex> , тогда гиперграф называется однородным или <tex>k</tex> - однородным, или <tex>k</tex> - гиперграфом. Обычный граф является 2-однородным гиепрграфом.
+
Так например гиперграф на рис. 5 является <tex> \alpha </tex>-ацикличным, но не является <tex> \beta </tex>-ацикличным, так как его подгиперграф на рис. 6 является <tex> \alpha </tex>-цикличным.
  
Степенью <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>.
+
== Источники информации ==
 +
* [https://en.wikipedia.org/wiki/Claude_Berge wikipedia.com — Клауд Берж]
 +
* [https://en.wikipedia.org/wiki/Hypergraph wikipedia.com — Гиперграфы]
 +
* [http://www.sciencedirect.com/science/article/pii/S0012365X09003446?np=y sciencedirect.com — Ацикличность в гиперграфах]
  
Гиперграф называется '''вершинно-транзитивным'''(или '''вершинно-симметричным'''), если все вершины симметричны. Точно так же, гиперграф называется '''реберно-транзитивным'''6 если все его ребра симметричны. Если гиперграф и вершинно-тразитивный, и реберно-транзитивный , тогда гиперграф называется '''транзитивным'''.
+
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Основные определения теории графов]]

Текущая версия на 19:07, 4 сентября 2022

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


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

Рис. 1: Гиперграф с множеством вершин [math]V = \{ v_1, v_2, v_3, v_4, v_5, v_6, v_7 \}[/math] и гиперребрами [math]E = \{ \{ v_1, v_2, v_3 \} , \{ v_2, v_3 \} , \{ v_3, v_5, v_6 \} , \{ v_4 \} \}[/math]


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

Определение:
Путем (англ. path) между двумя гиперребрами [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 \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]e_1[/math] [math]e_2[/math] [math]e_3[/math] [math]e_4[/math]
[math]v_1[/math]
[math]v_2[/math]
[math]v_3[/math]
[math]v_4[/math]
[math]v_5[/math]
[math]v_6[/math]
[math]v_7[/math]


[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]s[/math] в гиперграфе [math]H = (V, E)[/math] называется последовательность [math]( A_0, v_0, A_1, \ldots , A_{s - 1}, v_{s - 1}, A_s)[/math] , где [math]A_0 , \ldots , A_{s - 1} -[/math] различные ребра [math]H[/math] , ребро [math]A_s[/math] совпадает с [math]A_0[/math] , а [math]v_0, \ldots , v_{s - 1} -[/math] различные вершины [math]H[/math] , причем [math]v_i \in A_i \cap A_{i+1}[/math] для всех [math] i = 0, \ldots , s - 1[/math].


Рис. 3: Простейший случай цикла в гиперграфе


Универсальным способом задания гиперграфа является кенигово представление.


Определение:
Кенигово представление гиперграфа [math] H = (V, E) -[/math] обыкновенный двудольный граф [math]K(H)[/math] , отражающий отношение инцидентности различных элементов гиперграфа, с множеством вершин [math]V \cup E [/math] и долями [math]V, E[/math].


Первым, кто дал определение ацикличности гипергафа является Клауд Берж:

Теорема:
Гиперграф [math]H[/math] не содержит циклов в том случае, если его кенигово представление [math]-[/math] ацикличный граф, сожержит в противном случае.

Таким образом, если у нас есть цикл в графе кенигова представления, значит и сам гиперграф имеет цикл.

Рис. 4: Пример гиперграфа, содержащего цикл

Алгоритм нахождения цикла в гиперграфе

Поскольку гиперграф может задаваться кениговым представлением, тогда произведём серию поисков в глубину в двудольном графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе - в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл (если граф неориентированный, то случаи, когда поиск в глубину из какой-то вершины пытается пойти в предка, не считаются).

Ацикличность гиперграфов

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


Определение:
Гиперграф называется уменьшенным (англ. reduced) , если он эквивалентен своей редукции, то есть не имеет гиперребер внутри других гиперребер.


Пусть [math]M - [/math] множество вершин гиперграфа [math]H = (V, E)[/math]. Множество частичных ребер (англ. partial edges), порожденных множеством [math]M[/math], определяется как множество, полученное путем пересечения гиперребер из множества [math]E[/math] с [math]M[/math]. Таким образом, получаем множество : [math] \{ e \cap M : e \in E \} - \{ \emptyset \} [/math] и берем его редукцию.

Множество частичных ребер, порожденное из гиперграфа [math]H[/math] множеством [math]M[/math], называется вершинно-порожденным (англ. node-generated) множеством частичных ребер.


Определение:
Блоком (англ. block) уменьшенного гиперграфа называется связное, вершинно - порожденное множество частичных ребер без сочленения.


Определение:
Множество частичных ребер называется тривиальным (англ. trivial), если оно содержит одно гиперребро.


Определение:
Уменьшенный гиперграф называется [math] \alpha [/math] - ацикличным (англ. [math] \alpha [/math]-acyclity) , если всего его блоки тривиальны, иначе называют [math] \alpha [/math]-цикличным (англ. [math] \alpha[/math]-cyclity).


Пример

Рис. 5: [math] \alpha[/math]-ацикличный гиперграф
Рис. 6: Подмножество гиперребер [math] \{ ABC, CDE, EFA\} [/math]





Очень просто проверить что на рис. 3 представлен [math] \alpha [/math]-ацикличный гиперграф. Он содержит четыре гиперребра [math]- ABC, CDE, EFA, ACE[/math]. Сочленение для всего множества гиперребер является [math] ABC \cap ACE = AC [/math] , так как после удаления вершин [math]A[/math] и [math]C[/math] гиперграф не будет связным (вершина [math]B[/math] не будет ни с кем соединена). Заметим, что на рис. 6 подмножетсво гиперребер [math]\{ ABC, CDE, EFA \}[/math] не имеет сочленения. Однако, это множество не является вершинно - порожденным , таким образом, нет никаких противоречий с предположением, что гиперграф на рис. 5 является [math] \alpha [/math]-ацикличным.


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


Определение:
Гиперграф [math]H = (V, E) [/math] является [math] \beta [/math]-ацикличным (англ. [math] \beta [/math]-acyclity) , если все его подгиперграфы [math] \alpha [/math]-ацикличны.


Так например гиперграф на рис. 5 является [math] \alpha [/math]-ацикличным, но не является [math] \beta [/math]-ацикличным, так как его подгиперграф на рис. 6 является [math] \alpha [/math]-цикличным.

См. также

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