Гиперграфы

В математике гиперграф - это обобщение графа, у которого ребра могут соединять любое количество вершин. Более формально, гиперграф [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]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 \equiv G[/math] тогда и только тогда, когда [math]H^* \simeq 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].