Изменения

'''Гиперграфом''' (англ. ''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>]]    

'''Путем''' (англ. ''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>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>.

<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>.

Так например, для гиперграфа на рис.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>||||||||}

      ==Ацикличность гиперграфаЦикл в гиперграфе==

'''ЦикломПростым циклом''' длины <tex>s</tex> в гиперграфе <tex>H = (XV, E)</tex> называется последовательность гиперребер <tex>(e_A_0, v_0, A_1, \ldots , A_{i_1s - 1}, e_v_{i_2s - 1}, A_s)</tex> , где <tex>A_0 , \ldots , e_A_{i_ks - 1})-</tex> удовлетворяющим следующим свойствам:# различные ребра <tex>e_{i_k} = e_{i_1}H</tex># Для , ребро <tex>2 \le j \le k - 2A_s</tex> совпадает с выполняется <tex>A_0</tex> , а <tex>v_0, \forall e \in E : (S_ldots , v_{js -1} \cup S_j \cup S_{j+1}) \setminus e \ne \emptyset -</tex> различные вершины <tex>H</tex>, где причем <tex>S_j = e_{i_j} v_i \in A_i \cap e_{i_A_{ji+1}}</tex> для всех <tex> 1 i = 0, \le j \le k ldots , s - 1</tex>.

Для определения ацикличного гиперграфа введем определение '''уха''' гиперграфа, а также редукцию GYO(Graham-Yu-Ozsoyoglu)[[Файл:Cycle_hyper.jpg|thumb|450px|center|Рис. 3: Простейший случай цикла в гиперграфе]]

{{Определение|definition='''Ухом''' (англ. ear) Универсальным способом задания гиперграфа называется такое гиперребро <tex>e</tex>, что его вершины можно разделить на две группы:# Вершины, которые принадлежат только гиперребру <tex>e</tex> и никакому более.# Вершины, которые принадлежат другим гиперребрамявляется кенигово представление.}}

Определение '''редукции GYOКенигово представление''' гиперграфа <tex> H = (англ. GYO reductionV, E) -</tex> обыкновенный двудольный граф '''<tex>K(H) содержит всего два шага:# Устранение </tex>''' , отражающий отношение инцидентности различных элементов гиперграфа, с множеством вершин<tex>V \cup E </tex> и долями <tex>V, которые содержатся только в одном гиперребре.# Удаление гиперребер, которые содержатся в другихE</tex>.

То естьПервым, мы удаляем вершины которые содержатся в ухе, и ни в каком более гиперребре. Затем удаляем гиперребра, оставляя другие вершины.кто дал определение ацикличности гипергафа является Клауд Берж:

{{УтверждениеТеорема

Если гиперграф сводится к пустому с помощью редукции GYOГиперграф <tex>H</tex> не содержит циклов в том случае, тогда он если его кенигово представление <tex>-</tex> ацикличныйграф, сожержит в противном случае.

Таким образом, если у нас есть цикл в графе кенигова представления, значит и сам гиперграф имеет цикл. [[Файл:Acyclic_hyperCycle_example.png|thumb|450pxcenter|left500px|Рис.3 Ацикличный гиперграф4: Пример гиперграфа, содержащего цикл]] ===Алгоритм нахождения цикла в гиперграфе=== Поскольку гиперграф может задаваться кениговым представлением, тогда произведём серию поисков в глубину в двудольном графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе - в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл (если граф неориентированный, то случаи, когда поиск в глубину из какой-то вершины пытается пойти в предка, не считаются).