44
правки
Изменения
sta
Связный граф <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>H \simeq G</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 simeq G</tex> тогда и только тогда, когда <tex>H^* \simeq G^*</tex> Когда ребра гиперграфа явно помечены, то появляется дополнительное понятие '''сильного изоморфизима'''. Говорят, что <tex>H</tex> '''сильно изоморфен''' <tex>G</tex> , если перестановка является тождественной. Записывается как <tex>H \cong G</tex>. Стоит отметить, что все строго изоморфный графы изоморфны, но не наоборот. Когда вершины гиперграфа явно помечены, то появляется понятие '''эквивалентности''', а также '''равенства'''. Говорят, что <tex>H</tex> эквивалентен <tex>G</tex>, записывается как <tex>H \equiv G</tex>, если изоморфизм <tex>w</tex> имеет следующие свойства <tex>w(x_n) = y_n</tex> и <tex>w(e_i) = f_{\pi(i)}</tex> Заметим, что <tex>H \equiv G</tex> если, и только если <tex>H^* \cong G^*</tex>.Если, кроме того, перестановка <tex>\pi</tex> тождественна, то говорят, что <tex>H</tex> равен <tex>G</tex>, и записывается как <tex>H = G</tex>. Стоит отметить, что при таком определении равенства, графы самодвойственны, т.е. <tex>(H^*)^*= H</tex>. '''Автоморфизмом''' гиперграфа называется изоморфизм из множества вершин в них же, т.е. переобозначение вершин. Пример. Рассмотрим гиперграфы с ребрами <tex>H = \{ e_1 = \{ a, b \}, e_2 = \{ b, c\}, e_3 = \{ c, d \}, e_4 = \{d, a\}, e_5 = \{b, d \}, e_6 = \{a, c \}\}</tex> <tex>G = \{ f_1 = \{\alpha, \beta\}, f_2 = \{\beta,\gamma\}, f_3 = \{\gamma,\delta\}, f_4 = \{\delta,\alpha\},f_5=\{\alpha,\gamma\},f_6=\{\beta,\delta\}\}</tex> Тогда, очевидно, <tex>H</tex> и <tex>G</tex> изоморфны(с <tex>w(a) = \alpha</tex>, и т.д.), но они не строго изоморфны. Так, например, в <tex>H</tex> вершина <tex>a</tex> содержится в ребрах <tex>1, 4</tex> и <tex>6</tex>, так что <tex> e_1 \cap e_4 \cap e_6 = \{a\}</tex> Однако в <tex>G</tex> не существует вершины, которая содержится в ребрах <tex> 1, 4</tex> и <tex>6</tex>: <tex> f_1 \cap f_4 \cap f_6 = \emptyset </tex> В этом примере <tex>H</tex> и <tex>G</tex> эквивалентны, <tex>H \equiv G</tex>, и двойственные строго изоморфны: <tex>H^* \cong G^*</tex>.
==Ацикличность==
Транспонированная матрица <tex>A^t</tex> инцидентной матрицы определяет гиперграф <tex>H^* = (V^*, E^*)</tex> называемая двойственной к <tex>H</tex> , где <tex>V^*</tex> явялется <tex>m</tex>-ым элементом множества и <tex>E^*</tex> является <tex>n</tex>-ым элементом множества подмножества <tex>V^*</tex>. Для <tex>v^*_j \in V^*</tex> и <tex>e^*_i \in E^*, v^*_j \in e^*_i</tex> если, и только если <tex>a_{ij} = 1</tex>.
==Симметричные гиепрграфы==
'''Рангом''' <tex>r(H)</tex> гиперграфа <tex>H</tex> называется максимальная мощность любого из гиперребер в гиперграфе. Если все ребра имеют одинаковыую мощность <tex>k</tex> , тогда гиперграф называется однородным или <tex>k</tex> - однородным, или <tex>k</tex> - гиперграфом. Обычный граф является 2-однородным гиепрграфом.
Степенью <tex>d(v)</tex> вершины <tex>v</tex> называется число гиперребер, которые содержат <tex>v</tex>. <tex>H</tex> называется'''<tex>k</tex>- регулярным''', если каждая вершина имеет степень <tex>k</tex>.
Две вершины <tex>x</tex> и <tex>y</tex> гиперграфа <tex>H</tex> называются симметричными, если существует такой автоморфизм, что <tex>w(x) = y</tex>. Тва ребра <tex>e_i</tex> и <tex>e_j</tex> называются симметричными, если существет такой автоморфизм, что <tex>w(e_i) = e_j</tex>.
Гиперграф называется '''вершинно-транзитивным'''(или '''вершинно-симметричным'''), если все вершины симметричны. Точно так же, гиперграф называется '''реберно-транзитивным'''6 если все его ребра симметричны. Если гиперграф и вершинно-тразитивный, и реберно-транзитивный , тогда гиперграф называется '''транзитивным'''.
