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

Материал из Викиконспекты
Перейти к: навигация, поиск
(sta)
(sta)
Строка 22: Строка 22:
 
Связный граф <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>'.
 
Связный граф <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>'.
  
==Изоморфность и эквивалентсность==
+
==Изоморфность и эквивалентность==
Гиперграф <tex>H = (X, E)</tex> изоморфен гиперграфу <tex>G = (Y, F)</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>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>w</tex> называется изоморфизмом гиперграфов. Стоит отметить, что  
<tex>H \equiv G</tex> тогда и только тогда, когда <tex>H^* \simeq G</tex>*
+
<tex>H \simeq G</tex> тогда и только тогда, когда <tex>H^* \simeq G^*</tex>
 +
 
 +
Когда ребра гиперграфа явно помечены, то появляется дополнительное понятие '''сильного изоморфизима'''. Говорят, что <tex>H</tex> '''сильно изоморфен''' <tex>G</tex> , если перестановка является тождественной. Записывается как <tex>H \cong G</tex>. Стоит отметить, что все строго изоморфный графы изоморфны, но не наоборот.
 +
 
 +
Когда вершины гиперграфа явно помечены, то появляется понятие '''эквивалентности''', а также  '''равенства'''. Говорят, что <tex>H</tex> эквивалентен <tex>G</tex>, записывается как <tex>H \equiv G</tex>, если изоморфизм <tex>w</tex> имеет следующие свойства
 +
 
 +
<tex>w(x_n) = y_n</tex>
 +
 
 +
и
 +
 
 +
<tex>w(e_i) = f_{\pi(i)}</tex>
 +
 
 +
Заметим, что <tex>H \equiv G</tex> если, и только если <tex>H^* \cong G^*</tex>.
 +
Если, кроме того, перестановка <tex>\pi</tex> тождественна, то говорят, что <tex>H</tex> равен <tex>G</tex>, и записывается как <tex>H = G</tex>. Стоит отметить, что при таком определении равенства, графы самодвойственны, т.е. <tex>(H^*)^* = H</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> содержится в ребрах  <tex>1, 4</tex> и <tex>6</tex>, так что
 +
 
 +
<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>
 +
 
 +
В этом примере <tex>H</tex> и <tex>G</tex> эквивалентны, <tex>H \equiv G</tex>, и двойственные строго изоморфны: <tex>H^* \cong G^*</tex>.
 +
 
  
 
==Ацикличность==
 
==Ацикличность==
Строка 50: Строка 87:
  
 
Транспонированная матрица  <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>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>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 если все его ребра симметричны. Если гиперграф и вершинно-тразитивный, и реберно-транзитивный , тогда гиперграф называется '''транзитивным'''.

Версия 17:58, 22 декабря 2016

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

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

Частный случай гипергафа, где [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]2[/math].

Определения

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


Подгиперграфом называют гиперграф с некоторым множеством удаленных вершин. Формально, подгиперграф [math]H_a[/math] , индуцированный подмножеством [math]A[/math] множества [math] X [/math], который определен как 
[math]H_a = (A, \{e_i \cap A| e_i \cap A \neq \emptyset \}).[/math]

Частичным гипергафом называется гиперграф, с множеством удаленных ребер. Данное подмножество [math]J \subset I_e [/math] множества индексов ребер, частичный граф сгенерирован с помощью [math]J[/math], т.е [math](X, \{ e_i | i \in J \}).[/math]

Пусть дано множество [math]A \subseteq X[/math], разрезом гиперграфа называют такой частичный гиперграф [math]
H \times A = (A, \{e_i | i \in I_e, e_i \subseteq A \}).[/math]

Двойственным гиперграфом [math]H[/math]* к [math]H[/math] называют такой гиперграф, в котором поменяны местами вершины и ребра таким образом, что вершины определяются как [math]\{e_i\}[/math] и ребра определяются как [math]\{X_m\}[/math], где [math]X_m = \{ e_i | x_m \in e_i \}.[/math]

Когда операция равенства определена, как показано ниже, операция взятия двойственного гиперграфа выглядит следующим образом
[math](H^*)^* = H.[/math]

Связный граф [math]G[/math] с тем же множеством вершин, что и у связного гиперграфа [math]H[/math] называется «принимающим» графом для [math]H[/math], если каждое гиперребро [math]H[/math] включает связный подграф в [math]G[/math]. Для несвязного гиперграфа [math]H[/math] , [math]G[/math] является «принимающим», если существует биекция между связными компонентами [math]G[/math] и [math]H[/math] , так что каждая связная компонента [math]G[/math]' графа [math]G[/math] является принимающей для соответствующего [math]H[/math]'.

Изоморфность и эквивалентность

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

Когда ребра гиперграфа явно помечены, то появляется дополнительное понятие сильного изоморфизима. Говорят, что [math]H[/math] сильно изоморфен [math]G[/math] , если перестановка является тождественной. Записывается как [math]H \cong G[/math]. Стоит отметить, что все строго изоморфный графы изоморфны, но не наоборот.

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

[math]w(x_n) = y_n[/math]

и

[math]w(e_i) = f_{\pi(i)}[/math]

Заметим, что [math]H \equiv G[/math] если, и только если [math]H^* \cong G^*[/math]. Если, кроме того, перестановка [math]\pi[/math] тождественна, то говорят, что [math]H[/math] равен [math]G[/math], и записывается как [math]H = G[/math]. Стоит отметить, что при таком определении равенства, графы самодвойственны, т.е. [math](H^*)^* = H[/math].

Автоморфизмом гиперграфа называется изоморфизм из множества вершин в них же, т.е. переобозначение вершин.

Пример.

Рассмотрим гиперграфы с ребрами


[math]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 \}\}[/math]


[math]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\}\}[/math]


Тогда, очевидно, [math]H[/math] и [math]G[/math] изоморфны(с [math]w(a) = \alpha[/math], и т.д.), но они не строго изоморфны. Так, например, в [math]H[/math] вершина [math]a[/math] содержится в ребрах [math]1, 4[/math] и [math]6[/math], так что

[math] e_1 \cap e_4 \cap e_6 = \{a\}[/math]

Однако в [math]G[/math] не существует вершины, которая содержится в ребрах [math] 1, 4[/math] и [math]6[/math]:

[math] f_1 \cap f_4 \cap f_6 = \emptyset [/math]

В этом примере [math]H[/math] и [math]G[/math] эквивалентны, [math]H \equiv G[/math], и двойственные строго изоморфны: [math]H^* \cong G^*[/math].


Ацикличность

В отличие от обычных неориентированных графов, для которых существует только одно понятие ацикличности, существует множество неэквивалентных определений ацикличности гиперграфов.

Первое определение ацикличности для гиперграфов было дано Клаудом Бержем: гиперграф называется ацикличным по Бержу, если инцидентный ему граф ацикличный. Это определение достаточно ограничено. Например, если гиперграф имеет какую-то пару вершин [math]v \ne v'[/math] и какую-то пару гиперребер [math]f \ne f'[/math], таких что [math]v, v' \in f[/math] и [math]v, v' \in f'[/math], тогда имеет место цикл по Бержу. Цикличность по Бержу может быть найдена за линейное время с помощью исследования инцидентности гиперграфа.

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

Стоит отметить, что [math]\alpha[/math] - ацикличность графа имеет некоторое нелогичное свойство, а именно, что при добавлении к [math]\alpha[/math] - цикличному графу гиперребер гиперграф может стать [math]\alpha[/math] - ацикличным. Например, добавление гиперребра, которое содержит все вершина гиперграфа, всегда будет давать [math]\alpha[/math] - ацикличность графа. Частично мотивированным этим недостатком, Рональд Феджин определил более сильные понятия - [math]\beta[/math] - ацикличность и [math]\gamma[/math] - ацикличность. Можно констатировать [math]\beta[/math] - ацикличность как требование, чтобы все подгиперграфы исходного гиперграфа были [math]\alpha[/math] - ацикличными, что ээквивалентно выше упомянотому определению Грэхема. Понятие [math]\gamma[/math] - ацикличности имеет более ограниченное определение, которое эквивалентно несколькими желательными свойствами схем баз данных и связана с диаграммами Бахмена. <tex<\beta</tex> - ацикличность и [math]\gamma[/math] - ацикличность может быть найдена за полиномиальное время.

Матрица инцидентности

Пусть [math]V = \{ v_1, v_2, ... , v_n \},[/math] и [math]E = \{ e_1, e_2, ..., e_m \}[/math]. Каждый гиперграф имеет [math]n \times m[/math] инцидентную матрицу [math]A = (a_{ij}) [/math], где

[math] a_{ij} = \left \{ \begin{array}{ll} 1,& v_i \in e_j \\ 0,& otherwise \end{array} \right. [/math]

Транспонированная матрица  [math]A^t[/math] инцидентной матрицы определяет гиперграф [math]H^* = (V^*, E^*)[/math] называемая двойственной к [math]H[/math] , где [math]V^*[/math] явялется [math]m[/math]-ым элементом множества и [math]E^*[/math] является [math]n[/math]-ым элементом множества подмножества [math]V^*[/math]. Для [math]v^*_j \in V^*[/math] и [math]e^*_i \in E^*, v^*_j \in e^*_i[/math] если, и только если [math]a_{ij} = 1[/math].

Симметричные гиепрграфы

Рангом [math]r(H)[/math] гиперграфа [math]H[/math] называется максимальная мощность любого из гиперребер в гиперграфе. Если все ребра имеют одинаковыую мощность [math]k[/math] , тогда гиперграф называется однородным или [math]k[/math] - однородным, или [math]k[/math] - гиперграфом. Обычный граф является 2-однородным гиепрграфом.

Степенью [math]d(v)[/math] вершины [math]v[/math] называется число гиперребер, которые содержат [math]v[/math]. [math]H[/math] называется[math]k[/math]- регулярным, если каждая вершина имеет степень [math]k[/math].

Две вершины [math]x[/math] и [math]y[/math] гиперграфа [math]H[/math] называются симметричными, если существует такой автоморфизм, что [math]w(x) = y[/math]. Тва ребра [math]e_i[/math] и [math]e_j[/math] называются симметричными, если существет такой автоморфизм, что [math]w(e_i) = e_j[/math].

Гиперграф называется вершинно-транзитивным(или вершинно-симметричным), если все вершины симметричны. Точно так же, гиперграф называется реберно-транзитивным6 если все его ребра симметричны. Если гиперграф и вершинно-тразитивный, и реберно-транзитивный , тогда гиперграф называется транзитивным.