Изменения

Перейти к: навигация, поиск

Гиперграфы

167 байт добавлено, 22:56, 5 января 2017
Нет описания правки
{{Определение
|definition=
'''Гиперграфом''' (англ. ''hypergraph'') <tex>H</tex> называют такую пару <tex>H = (X, E)</tex> , где <tex>X - </tex> множество вершин, а <tex>E -</tex> семейство подмножеств <tex>X</tex> , называемых '''гиперребрами''' (англ. ''hyperedges'')
}}
Обычные графы, у которых ребра могут соединять только две вершины, являются частным случаем гиперграфа, у которых все гиперребра содержат только две вершины.
[[Файл:Hypergraph.jpg|thumb|450px|right|Рис.1Частный случай гипергафа: Гиперграф с множеством вершин <tex>V = \{ v_1, v_2, v_3, v_4, v_5, v_6, v_7 \}</tex> и гиперребрами <tex>E = \{ \{ v_1, v_2, v_3 \} , \{ v_2, v_3 \} , \{ v_3, v_5, v_6 \} , \{ v_4 \} \}</tex>]]        
==Основные понятия гиперграфов==
{{Определение
|definition=
'''Путем''' (англ. ''path, смотри также [[Основные_определения_теории_графов#.D0.9F.D1.83.D1.82.D0.B8_.D0.B2_.D0.B3.D1.80.D0.B0.D1.84.D0.B0.D1.85|путь в обычном графе]]'') между двумя гиперребрами <tex>e_i</tex> и <tex>e_j</tex> гиперграфа <tex>H</tex> называется последовательность гиперребер <tex>e_{u_1}, e_{u_2} , \ldots ,e_{u_k}</tex> таких что :
# <tex>e_{u_1} = e_i </tex> и <tex>e_{u_k} = e_j</tex>
# <tex>\forall v: 1 \leqslant v \leqslant k-1, e_v \cap e_{v+1} \ne \emptyset</tex>
{{Определение
|definition=
Гиперграф <tex>H</tex> называется '''связным''' (англ. ''connected'') тогда и только тогда, когда существует путь между каждой парой гиперребер.
}}
[[Файл:Connected_hypergraph.jpg‎|thumb|450px|center|Рис.2 : Связный гиперграф]]
Пусть <tex>E- </tex> - набор гиперребер, <tex>e_1</tex> и <tex>e_2- </tex> - элементы <tex>E</tex> и <tex>q = e_1 \cap e_2</tex>.
{{Определение
|definition=
<tex>q</tex> называется '''сочленением''' (англ. ''articulation'') <tex>E</tex> , если при его удалении из всех гиперребер <tex>E</tex>, множество разрывается.
}}
На Рисрис.2 <tex>q = e_4 \cap e_6 = \{ x_{12}, x_{13}\}</tex> является сочленением <tex>E</tex>.
==Матрица инцидентности ==
</tex>
Так например, для гиперграфа на рис.1 мы имеем такую можем построить матрицу инцидентностипо таблице отношения принодлежности вершины к гиперребру: {| class="wikitable" align="left" style="color: black; background-color:#ffffcc;" cellpadding="10"|+!!<tex>e_1</tex>!<tex>e_2</tex>!<tex>e_3</tex>!<tex>e_4</tex>|-align="center"!<tex>v_1</tex>|✓|||| |||-align="center"!<tex>v_2</tex>|✓||✓|| |||-align="center" !<tex>v_3</tex>|✓||✓||✓|| |-align="center" !<tex>v_4</tex>| |||| ||✓|-align="center" !<tex>v_5</tex>|||||✓|| |-align="center" !<tex>v_6</tex>|||||✓|| |-align="center" !<tex>v_7</tex>||||||||}
0 & 0 & 0 & 0\\
\end{pmatrix}</tex>
 
==Ацикличность гиперграфа==
 
{{Определение
|definition=
'''Циклом''' в <tex>H = (X, E)</tex> называется последовательность гиперребер <tex>(e_{i_1}, e_{i_2}, \ldots , e_{i_k})</tex> удовлетворяющим следующим свойствам:
# <tex>e_{i_k} = e_{i_1}</tex>
# Для <tex>2 \le j \le k - 2</tex> выполняется <tex>\forall e \in E : (S_{j-1} \cup S_j \cup S_{j+1}) \setminus e \ne \emptyset </tex>, где <tex>S_j = e_{i_j} \cap e_{i_{j+1}}</tex> для <tex> 1 \le j \le k - 1</tex>
}}
 
[[Файл:Cycle_hyper.jpg|thumb|left|450px|Простейший случай цикла в гиперграфе]]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
==Ацикличность в гиперграфе==
{{Определение
|definition=
'''Простым циклом''' длины <tex>s</tex> в гиперграфе <tex>H = (V, E)</tex> называется последовательность <tex>( A_0, v_0, A_1, \ldots , A_{s - 1}, v_{s - 1}, A_s)</tex> , где <tex>A_0 , \ldots , A_{s - 1} -</tex> различные ребра <tex>H</tex> , ребро <tex>A_s</tex> совпадает с <tex>A_0</tex> , а <tex>v_0, \ldots , v_{s - 1} -</tex> различные вершины <tex>H</tex> , причем <tex>v_i \in A_i \cap A_{i+1}</tex> для всех <tex> i = 0, \ldots , s - 1</tex>.
}}
[[Файл:Cycle_hyper.jpg|thumb|450px|center|Рис. 3: Простейший случай цикла в гиперграфе]]
Для определения ацикличного Универсальным способом задания гиперграфа введем определение '''уха''' гиперграфа, а также редукцию GYO(Graham-Yu-Ozsoyoglu)является кенигово представление.
{{Определение
|definition=
'''УхомКенигово представление''' гиперграфа <tex> H = (англ. earV, E) гиперграфа называется такое гиперребро -</tex> обыкновенный двудольный граф '''<tex>eK(H)</tex>''' , что его вершины можно разделить на две группы:# Вершиныотражающий отношение инцидентности различных элементов гиперграфа, которые принадлежат только гиперребру с множеством вершин <tex>eV \cup E </tex> и никакому более.# Вершиныдолями <tex>V, которые принадлежат другим гиперребрамE</tex>.
}}
 
Первым, кто дал определение ацикличности гипергафа является [https://en.wikipedia.org/wiki/Claude_Berge Клауд Берж]:
{{Определение
|definition=
Определение '''редукции GYO''' (англ. GYO reduction) Гиперграф <tex>H</tex> не содержит всего два шага:# Устранение вершинциклов в том случае, которые содержатся только в одном гиперребре.# Удаление гиперребересли его кенигово представление <tex>-</tex> ацикличный граф, которые содержатся сожержит в другихпротивном случае.
}}
То Таким образом, если у нас есть, мы удаляем вершины которые содержатся цикл в ухеграфе кенигова представления, значит и ни в каком более гиперребре. Затем удаляем гиперребра, оставляя другие вершины. {{Утверждение|statement=Если гиперграф сводится к пустому с помощью редукции GYO, тогда он ацикличный.}} [[Файл:Acyclic_hyper.png|thumb|450px|left|Рис.3 Ацикличный сам гиперграф]] С помощью редукции GYO удаляются вершины A, B и C (т.к они содержатся только в одном своем гиперребре), а затем удаляем оставшиеся внутренние гиперребраимеет цикл.                    
[[Файл:Cycle_example.png|thumb|center|500px|Рис. 4: Пример гиперграфа, содержащего цикл]]
== См. также ==
Ivan
44
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/58856»

Навигация