Гиперграфы

Определение:

Гиперграфом [math]H = (X, U; R)[/math] называется пара множеств [math]X = \{x_i / i \in I\}[/math], [math]U = \{u_j / j \in J\}[/math] вместе с двуместным предикатом [math]R \Leftrightarrow R(x, u)[/math], определенным при всех [math]x \in X[/math], [math]u \in U[/math], где [math]x \in X[/math] — вершины; [math]u \in U[/math] — ребра; предикат [math]R[/math] — инцидентор гиперграфа [math]H[/math]. Под элементом гиперграфа будем понимать его вершину или ребро, т. е. любой элемент множества [math]X \cup U[/math].

Гиперграф — такое обобщение неориентированного графа, когда ребрами могут служить произвольные подмножества заданного множества вершин, а не только двухвершинные и одно­вершинные.

Обыкновенный граф есть частный случай гиперграфа [math](X, U; R)[/math], когда [math]X \ne {\O}[/math], [math]\forall u \in U(|Х(u)| = 2)[/math] и [math]\forall u, v \in U [u \ne v] \Rightarrow [X(u) \ne X(v)][/math], а неориентированный граф общего вида — это гиперграф, удовлетворяющий условиям [math]X \ne {\O}[/math] и [math]\forall u \in U ((1 \leqslant |X(u)| \leqslant 2)^2)[/math].