Гиперграфы

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