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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
 
 
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
Строка 15: Строка 13:
 
'''Гиперграф''' — такое обобщение неориентированного графа, когда  
 
'''Гиперграф''' — такое обобщение неориентированного графа, когда  
 
ребрами могут служить произвольные подмножества заданного множества вершин, а не только двухвершинные и одно­вершинные.
 
ребрами могут служить произвольные подмножества заданного множества вершин, а не только двухвершинные и одно­вершинные.
 +
 +
Обыкновенный граф есть частный случай гиперграфа <tex>(X, U; R)</tex>, когда
 +
<tex>X \ne {\O}</tex>, <tex>\forall u \in U(|Х(u)| = 2)</tex> и <tex>\forall u, v \in U  [u \ne v] \Rightarrow [X(u) \ne X(v)]</tex>, а неориентированный граф общего вида — это гиперграф, удовлетворяющий условиям <tex>X \ne {\O}</tex> и <tex>\forall u \in U  ((1 \leqslant |X(u)| \leqslant 2)^2)</tex>.

Версия 11:25, 25 сентября 2015

Определение:
Гиперграфом [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].