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>w</tex> называется изоморфизмом гиперграфов. Стоит отметить, что
<tex>H \equiv G</tex> тогда и только тогда, когда <tex>H* \simeq G</tex>*
==Ацикличность==
В отличие от обычных неориентированных графов, для которых существует только одно понятие ацикличности, существует множество неэквивалентных определений ацикличности гиперграфов.
Первое определение ацикличности для гиперграфов было дано Клаудом Бержем: гиперграф называется ацикличным по Бержу, если инцидентный ему граф ацикличный. Это определение достаточно ограничено. Например, если гиперграф имеет какую-то пару вершин <tex>v \ne v'</tex> и какую-то пару гиперребер <tex>f \ne f'</tex>, таких что <tex>v, v' \in f</tex> и <tex>v, v' \in f'</tex>, тогда имеет место цикл по Бержу. Цикличность по Бержу может быть найдена за линейное время с помощью исследования инцидентности гиперграфа.
Также мы можем определить более слабое определение ацикличности гиперграфа, называемое <tex>\alpha</tex> - ацикличность. Это понятие ацикличности эквивалентно определению гиперграфа, который является конформальным(т.е. каждая клика исходного графа покрыта каким-то гиперребром), и при этом исходный граф является хордальным ; это также эквивалентно сводимости пустого графа через GYO алгоритм(более известный как алгоритм Грэхема), повторяющийся процесс, который удаляет гиперребра с использованием главного определения "ухо графа". В области теории баз данных известно, что схема баз данных обладает некоторыми желательными свойствами, если ее основной граф является <tex>\alpha</tex> - ациклическим. <tex>\alpha</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> - ацикличность может быть найдена за полиномиальное время.
