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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Start)
(sta)
Строка 1: Строка 1:
'''Гиперграфом''' (англ. ''hypergraph'') называется обобщение графа, в котором каждое ребро соединяет необязательно две вершины. Формально, '''гиперграф''' {{---}} упорядоченная пара <tex>H = (V,E)</tex>, где <tex>V</tex> {{---}} множество вершин гиперграфа, а <tex>E</tex> {{---}} множество ребер гиперграфа, где каждое ребро является подмножеством множества вершин.
+
В математике '''гиперграф''' - это обобщение графа, у которого ребра могут соединять любое количество вершин. Более формально, гиперграф <tex>H</tex> - это пара <tex>(X, E)</tex> , где <tex>X</tex> - множество элементов называемых узлами или вершинами, и <tex>E</tex> - не пустое подмножество <tex>X</tex> называемых гиперребрами или просто ребрами.
  
В дальнейшем будем считать, что все рассматриваемые гипергафы обладают свойствами:
+
В то время, как ребра графа соединяют две пары вершин, гиперребра - произвольные множества вершин, которые могут содержать любое количество вершин. Однако, очень часто рассматривают гиперграфы с гиперребрами одинаковой мощности ; <tex>k</tex> - равномерный гиперграф - это такой гиперграф, у которого все гиперребра имеют размер k. (Другими словами, такой гиперграф множество подмножеств, которые содержат k вершин). Так например, <tex>2</tex> - равномерный гиперграф - обычный граф.
 
 
*<tex>\forall i</tex> <tex> E_i \neq \emptyset </tex>
 
 
 
*<tex> \cup E = X </tex>
 
  
 
[[Файл:Hypergraph.jpg|right|thumb|Частный случай гипергафа, где <tex>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\}\}</tex>]]
 
[[Файл:Hypergraph.jpg|right|thumb|Частный случай гипергафа, где <tex>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\}\}</tex>]]
Строка 12: Строка 8:
 
==Определения==
 
==Определения==
  
'''Подгиперграфом''' (англ. ''subhypergraph'') <tex>H_1</tex> гиперграфа <tex>H=(V,E)</tex> назывется гипергаф: <tex>H_1 = (V_1, \{E_1 | \forall i: e_i \cap V_1 \neq \emptyset \})</tex>. Иначе, подгипергаф {{---}} это гипергаф с некоторомы удаленными вершинами.
+
Так как множество гиперребер может быть любой мощности, существуют несколько понятий '''подграфа''' гиперграфа, называемых '''подгиперграфами''', '''частичные гиперграфы''' и '''разрез гиперграфов'''. Пусть <tex>H = (X, E) </tex> - гиперграф содержащий множество вершин <tex>X = \{x_i | i \in I_v\}</tex> и множество ребер <tex>E = \{e_i | i \in I_e, e_i \subseteq X\}</tex>, где <tex>I_v</tex> и <tex>I_e</tex> множества индексов вершин и ребер соответсвенно.

 +
 
 +
'''Подгиперграфом''' называют гиперграф с некоторым множеством удаленных вершин. Формально, подгиперграф <tex>H_a</tex> , индуцированный подмножеством <tex>A</tex> множества <tex> X </tex>, который определен как 
<tex>H_a = (A, \{e_i \cap A| e_i \cap \neq \emptyset \}).</tex>
 +
 
 +
'''Частичным''' гипергафом называется гиперграф, с множеством удаленных ребер. Данное подмножество <tex>J \subset I_e </tex> множества индексов ребер, частичный граф сгенерирован с помощью <tex>J</tex>, т.е <tex>(X, \{ e_i | i \in J \}).</tex>
 +
 
 +
Пусть дано множество <tex>A \subseteq X</tex>, разрезом гиперграфа называют такой '''частичный''' гиперграф <tex>
H \times A = (A, \{e_i | i \in I_e, e_i \subseteq A \}).</tex>
 +
 
 +
'''Двойственным''' гиперграфом <tex>H</tex>* к <tex>H</tex> называют такой гиперграф, в котором поменяны местами вершины и ребра таким образом, что вершины определяются как <tex>\{e_i\}</tex> и ребра определяются как <tex>\{X_m\}</tex>, где <tex>X_m = \{ e_i | x_m \in e_i \}.</tex>
 +
 
 +
Когда операция равенства определена, как показано ниже, операция взятия '''двойственного''' гиперграфа выглядит следующим образом
<tex>(H*)* = H.</tex>
  
'''Реберным гиперграфом''' (англ. ''dual'') <tex>H^* = L(H)</tex> называется гипергаф: <tex>H^* = (V^*, E^*) = (E, V) = (\{e_1, e_2 \ldots\},\{v_1,v_2\ldots\}) = (\{v^*_1, v^*_2 \ldots\},\{e^*_1, e^*_2\ldots\})</tex>, где вершина <tex>v^*_i</tex> принадлежит ребру <tex>e^*_j</tex>, если вершина <tex>v_j</tex> принадлежит ребру <tex>e_i</tex> в исходном гиперграфе <tex>H</tex>. Оче
+
Связный граф <tex>G</tex> с тем же множеством вершин, что и у связного гиперграфа <tex>H</tex> называется «принимающим» графом для <tex>H</tex>, если каждое гиперребро <tex>H</tex> включает связный подграф в <tex>G</tex>. Для несвязного гиперграфа <tex>H</tex> , <tex>G</tex> является «принимающим», если существует биекция между связными компонентами <tex>G</tex> и <tex>H</tex> , так что каждая связная компонента <tex>G</tex>' графа <tex>G</tex> является принимающей для соответствующего <tex>H</tex>'.
  
==Свойства==
 
  
==Ацикличность==
+
==Изоморфность и эквивалентсность==
Заметим, что гиперграф удобно задавать матрицей инцидентности.
+
Гиперграф <tex>H = (X, E)</tex> изоморфен гиперграфу <tex>G = (Y, F)</tex> , если существует биекция <tex>w</tex> : <tex>X</tex> -> <tex>Y</tex>
 и перестановка <tex>\pi</tex> множества <tex>I</tex> такая, что <tex>w</tex><tex>(e_i)</tex> = <tex>f_\pi(i)</tex>
 +
Тогда биекция <tex>w</tex> называется изоморфизмом гиперграфов. Стоит отметить, что
 +
<tex>H \equiv G</tex> тогда и только тогда, когда <tex>H* \simeq G</tex>*

Версия 23:54, 12 декабря 2016

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