44
правки
Изменения
→Ацикличность в гиперграфе
==Ацикличность Цикл в гиперграфе==
{{Определение
[[Файл:Cycle_example.png|thumb|center|500px|Рис. 4: Пример гиперграфа, содержащего цикл]]
===Алгоритм нахождения цикла в гиперграфе===
Поскольку гиперграф может задаваться кениговым представлением, тогда произведём серию поисков в глубину в двудольном графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе - в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл (если граф неориентированный, то случаи, когда поиск в глубину из какой-то вершины пытается пойти в предка, не считаются).
==Ацикличность гиперграфов==
{{Определение
|definition=
'''Редукцией''' (англ. ''reduction'') гиперграфа <tex>H = (V, E)</tex> называется такой гиперграф <tex>H' = (V, E')</tex> , который получается из исходного путем удаления всех гиперребер, которые полностью содержатся в других гиперреберах.
}}
{{Определение
|definition=
Гиперграф называется '''уменьшенным''' (англ. ''reduced'') , если он эквивалентен своей редукции, то есть не имеет гиперребер внутри других гиперребер.
}}
Пусть <tex>M - </tex> множество вершин гиперграфа <tex>H = (V, E)</tex>. Множество '''частичных ребер''' (англ. ''partial edges'') , порожденных множеством <tex>M</tex> , определяется как множество, полученное путем пересечения гиперребер из множества <tex>E</tex> с <tex>M</tex>. Таким образом, получаем множество : <tex> \{ e \cap M : e \in E \} - \{ \emptyset \} </tex> и берем его редукцию.
Множество частичных ребер, порожденное из гиперграфа <tex>H</tex> множеством <tex>M</tex>, называется '''вершинно - порожденным''' (англ. ''node-generated'') множеством частичных ребер.
{{Определение
|definition=
'''Блоком''' (англ. ''block'') уменьшенного гиперграфа называется связное, вершинно - порожденное множество частичных ребер без сочленения.
}}
{{Определение
|definition=
Множество частичных ребер называется '''тривиальным''' (англ. ''trivial''), если оно содержит одно гиперребро.
}}
{{Определение
|definition=
Уменьшенный гиперграф называется '''<tex> \alpha </tex> - ацикличным''' (англ. ''<tex> \alpha </tex>-acyclity'') , если всего его блоки тривиальны, иначе называют '''<tex> \alpha </tex>-цикличным''' (англ. ''<tex> \alpha</tex>-cyclity'').
}}
''Пример''
[[Файл:Alpha-acyclity-1.png|thumb|lcenter|500px|Рис. 5: <tex> \alpha</tex>-ацикличный гиперграф]]
[[Файл:Alpha-acyclity-2.png|thumb|center|500px|Рис. 6: Подмножество гиперребер <tex> \{ ABC, CDE, EFA\} </tex>]]
Очень просто проверить что на рис. 3 представлен <tex> \alpha </tex>-ацикличный гиперграф. Он содержит четыре гиперребра <tex>- ABC, CDE, EFA, ACE</tex>. Сочленение для всего множества гиперребер является <tex> ABC \cap ACE = AC </tex> , так как после удаления вершин <tex>A</tex> и <tex>C</tex> гиперграф не будет связным (вершина <tex>B</tex> не будет ни с кем соединена). Заметим, что на рис. 6 подмножетсво гиперребер <tex>\{ ABC, CDE, EFA \}</tex> не имеет сочленения. Однако, это множество не является вершинно - порожденным , таким образом, нет никаких противоречий с предположением, что гиперграф на рис. 5 является <tex> \alpha </tex>-ацикличным.
Заметим, что <tex> \alpha </tex>-ацикличность имеет одно нелогичное свойство: при добавлении гиперребер к <tex> \alpha </tex>-цикличному гиперграфу он может стать <tex> \alpha </tex>-ацикличным (например, при добавлении гиперребра, которое охватывает все вершины, всегда будет делать гиперграф <tex> \alpha </tex>-ацикличным). Из-за этого свойства было введено более строгое определение, называемое <tex> \beta </tex>-ацикличностью.
{{Определение
|definition=
Гиперграф <tex>H = (V, E) </tex> является '''<tex> \beta </tex>-ацикличным''' (англ. ''<tex> \beta </tex>-acyclity'') , если все его подгиперграфы <tex> \alpha </tex>-ацикличны.
}}
Так например гиперграф на рис. 5 является <tex> \alpha </tex>-ацикличным, но не является <tex> \beta </tex>-ацикличным, так как его подгиперграф на рис. 6 является <tex> \alpha </tex>-цикличным.
== См. также ==
