44
правки
Изменения
sta
'''Двойственным''' гиперграфом <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>
Связный граф <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>*
==Ацикличность==
Стоит отметить, что <tex>\alpha</tex> - ацикличность графа имеет некоторое нелогичное свойство, а именно, что при добавлении к <tex>\alpha</tex> - цикличному графу гиперребер гиперграф может стать <tex>\alpha</tex> - ацикличным. Например, добавление гиперребра, которое содержит все вершина гиперграфа, всегда будет давать <tex>\alpha</tex> - ацикличность графа. Частично мотивированным этим недостатком, Рональд Феджин определил более сильные понятия - <tex>\beta</tex> - ацикличность и <tex>\gamma</tex> - ацикличность. Можно констатировать <tex>\beta</tex> - ацикличность как требование, чтобы все подгиперграфы исходного гиперграфа были <tex>\alpha</tex> - ацикличными, что ээквивалентно выше упомянотому определению Грэхема. Понятие <tex>\gamma</tex> - ацикличности имеет более ограниченное определение, которое эквивалентно несколькими желательными свойствами схем баз данных и связана с диаграммами Бахмена. <tex<\beta</tex> - ацикличность и <tex>\gamma</tex> - ацикличность может быть найдена за полиномиальное время.
==Матрица инцидентности==
Пусть <tex>V = \{ v_1, v_2, ... , v_n \},</tex> и <tex>E = \{ e_1, e_2, ..., e_m \}</tex>. Каждый гиперграф имеет <tex>n \times m</tex> инцидентную матрицу <tex>A = (a_{ij}) </tex>, где
<tex> a_{ij} = \left \{
\begin{array}{ll}
1,& v_i \in e_j \\
0,& otherwise
\end{array}
\right.
</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>.
