Гиперграфы

В математике гиперграф - это обобщение графа, у которого ребра могут соединять любое количество вершин. Более формально, гиперграф [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 если все его ребра симметричны. Если гиперграф и вершинно-тразитивный, и реберно-транзитивный , тогда гиперграф называется транзитивным.