Изменения

В математике {{Определение|definition='''гиперграфГиперграфом''' - это обобщение графа, у которого ребра могут соединять любое количество вершин(англ. Более формально, гиперграф ''hypergraph'') <tex>H</tex> - это пара называют такую пару <tex>H = (X, E)</tex> , где <tex>X- </tex> - множество элементов называемых узлами или вершинамивершин, и а <tex>E-</tex> - не пустое подмножество семейство подмножеств <tex>X</tex> , называемых '''гиперребрами или просто ребрами''' (англ.''hyperedges'') }}

В то времяОбычные графы, как у которых ребра графа соединяют могут соединять только две пары вершин, гиперребра - произвольные множества вершин, которые могут содержать любое количество вершин. Однаковершины, очень часто рассматривают гиперграфы с гиперребрами одинаковой мощности ; <tex>k</tex> - равномерный гиперграф - это такой гиперграфявляются частным случаем гиперграфа, у которого которых все гиперребра имеют размер k. (Другими словами, такой гиперграф множество подмножеств, которые содержат k вершин). Так например, <tex>2</tex> - равномерный гиперграф - обычный графтолько две вершины.

[[Файл:Hypergraph.jpg|rightthumb|thumb450px|Частный случай гипергафа, где Рис. 1: Гиперграф с множеством вершин <tex>EV =\{e_1v_1, e_2v_2, e_3v_3, e_4v_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>]]Стоит заметить, что обычный граф является частным случаем гиперграфа, где каждое ребро имеет мощность <tex>2</tex>.

'''Подгиперграфом''' называют гиперграф с некоторым множеством удаленных вершин. Формально, подгиперграф <tex>H_a</tex> , индуцированный подмножеством <tex>A</tex> множества <tex> X </tex>, который определен как 
<tex>H_a = (A, \{e_i \cap A| e_i \cap A \neq \emptyset \}).</tex>=Основные понятия гиперграфов==

{{Определение|definition='''ЧастичнымПутем''' гипергафом называется гиперграф, с множеством удаленных ребер(англ. Данное подмножество ''path'') между двумя гиперребрами <tex>e_i</tex> и <tex>J \subset I_e e_j</tex> множества индексов ребер, частичный граф сгенерирован с помощью гиперграфа <tex>JH</tex>, т.е называется последовательность гиперребер <tex>(Xe_{u_1}, e_{u_2} , \ldots ,e_{u_k}</tex> таких что :# <tex>e_{ u_1} = e_i | i </tex> и <tex>e_{u_k} = e_j</tex># <tex>\forall v: 1 \in J leqslant v \leqslant k-1, e_v \cap e_{v+1}).\ne \emptyset</tex>}}

Пусть дано множество {{Определение|definition=Гиперграф <tex>A \subseteq XH</tex>, разрезом гиперграфа называют такой называется '''частичныйсвязным''' гиперграф <tex>
H \times A = (Aангл. ''connected'') тогда и только тогда, \{e_i | i \in I_e, e_i \subseteq A \когда существует путь между каждой парой гиперребер.}}).</tex>

'''Двойственным''' гиперграфом <tex>H</tex>* к <tex>H</tex> называют такой гиперграф, в котором поменяны местами вершины и ребра таким образом, что вершины определяются как <tex>\{e_i\}</tex> и ребра определяются как <tex>\{X_m\}</tex>, где <tex>X_m = \{ e_i [[Файл:Connected_hypergraph.jpg‎|thumb|450px|center| x_m \in e_i \}Рис.</tex>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>(H^*)^* = H.E</tex>, множество разрывается.}}

Связный граф <tex>G</tex> с тем же множеством вершин, что и у связного гиперграфа <tex>H</tex> называется «принимающим» графом для <tex>H</tex>, если каждое гиперребро <tex>H</tex> включает связный подграф в <tex>G</tex>На рис. Для несвязного гиперграфа 2 <tex>H</tex> q = e_4 \cap e_6 = \{ x_{12}, <tex>G</tex> является «принимающим», если существует биекция между связными компонентами <tex>G</tex> и <tex>H</tex> , так что каждая связная компонента <tex>G</tex>' графа <tex>Gx_{13}\}</tex> является принимающей для соответствующего сочленением <tex>HE</tex>'.

==Изоморфность и эквивалентностьМатрица инцидентности ==Гиперграф <tex>H = (X, E)</tex> изоморфен гиперграфу <tex>G = (Y, F)</tex> , записывается как <tex>H \simeq G</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 \simeq G</tex> тогда и только тогда, когда <tex>H^* \simeq G^*</tex>

Когда ребра гиперграфа явно помеченыПусть дан гиперграф <tex>H = (X, то появляется дополнительное понятие '''сильного изоморфизима'''. ГоворятE)</tex> , что где <tex>HX = \{ x_1, x_2, \ldots , x_n \}</tex> '''сильно изоморфен''' и <tex>GE = \{ e_1, e_2, \ldots , e_m \}</tex> , если перестановка является тождественной. Записывается как Любой гиперграф может задаваться матрицей инцидентности (смотри [[Матрица_инцидентности_графа|матрицу инцидентности в обычном графе)]] <tex>H A = (a_{ij}) </tex> размером <tex> n \cong Gtimes m</tex>. Стоит отметить, что все строго изоморфный графы изоморфны, но не наоборот.где

Когда вершины гиперграфа явно помечены, то появляется понятие '''эквивалентности''', а также <tex> a_{ij} = \left \{ \begin{array}{ll} 0 & x_i \in e_j \\ 1 & \mathrm{otherwise} \end{array} '''равенства'''\right. Говорят</tex> Так например, что для гиперграфа на рис.1 мы можем построить матрицу инцидентности по таблице отношения принодлежности вершины к гиперребру: {| class="wikitable" align="left" style="color: black; background-color:#ffffcc;" cellpadding="10"|+!!<tex>He_1</tex> эквивалентен !<tex>Ge_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>H \equiv GA = </tex>, если изоморфизм <tex>w\begin{pmatrix}1 & 0 & 0 & 0\\1 & 1 & 0 & 0\\1 & 1 & 1 & 0\\0 & 0 & 0 & 1\\0 & 0 & 1 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 0\\\end{pmatrix}</tex> имеет следующие свойства        ==Цикл в гиперграфе==

{{Определение|definition='''Простым циклом''' длины <tex>s</tex> в гиперграфе <tex>wH = (x_nV, 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 = y_n0, \ldots , s - 1</tex>. }}

Заметим, что <tex>H \equiv G</tex> если, и только если <tex>H^* \cong G^*</tex>.Если, кроме того, перестановка <tex>\pi</tex> тождественна, то говорят, что <tex>H</tex> равен <tex>G</tex>, и записывается как <tex>H = G</tex>. Стоит отметить, что при таком определении равенства, графы самодвойственны, т.е. <tex>(H^*)^* = H</tex>Универсальным способом задания гиперграфа является кенигово представление.

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

<tex>H = \{ e_1 = \{ a[[Файл:Cycle_example.png|thumb|center|500px|Рис. 4: Пример гиперграфа, b \}, e_2 = \{ b, c\}, e_3 = \{ c, d \}, e_4 = \{d, a\}, e_5 = \{b, d \}, e_6 = \{a, c \}\}</tex>содержащего цикл]]

<tex>G = \{ f_1 = \{\alphaПоскольку гиперграф может задаваться кениговым представлением, \beta\}тогда произведём серию поисков в глубину в двудольном графе. Т.е. из каждой вершины, f_2 = \{\betaв которую мы ещё ни разу не приходили,\gamma\}запустим поиск в глубину, f_3 = \{\gammaкоторый при входе в вершину будет красить её в серый цвет,\delta\}а при выходе - в чёрный. И если поиск в глубину пытается пойти в серую вершину, f_4 = \{\deltaто это означает,\alpha\}что мы нашли цикл (если граф неориентированный,f_5=\{\alphaто случаи,\gamma\}когда поиск в глубину из какой-то вершины пытается пойти в предка,f_6=\{\beta,\delta\}\}</tex>не считаются).

Тогда, очевидно, {{Определение|definition='''Редукцией''' (англ. ''reduction'') гиперграфа <tex>H= (V, E)</tex> и называется такой гиперграф <tex>G</tex> изоморфныH' = (с <tex>w(aV, E') = \alpha</tex>, и т.д.)который получается из исходного путем удаления всех гиперребер, но они не строго изоморфныкоторые полностью содержатся в других гиперреберах. Так, например, в <tex>H</tex> вершина <tex>a</tex> содержится в ребрах <tex>1, 4</tex> и <tex>6</tex>, так что }}

<tex> e_1 \cap e_4 \cap e_6 {{Определение|definition= \{a\Гиперграф называется '''уменьшенным''' (англ. ''reduced'') , если он эквивалентен своей редукции, то есть не имеет гиперребер внутри других гиперребер.}}</tex>

Однако в Пусть <tex>GM - </tex> не существует вершинымножество вершин гиперграфа <tex>H = (V, которая содержится в ребрах E)</tex> 1. Множество '''частичных ребер''' (англ. ''partial edges''), 4порожденных множеством <tex>M</tex> и , определяется как множество, полученное путем пересечения гиперребер из множества <tex>E</tex> с <tex>6M</tex>. Таким образом, получаем множество :<tex> \{ e \cap M : e \in E \} - \{ \emptyset \} </tex> и берем его редукцию.

Множество частичных ребер, порожденное из гиперграфа <tex> f_1 \cap f_4 \cap f_6 = \emptyset H</tex>множеством <tex>M</tex>, называется '''вершинно-порожденным''' (англ. ''node-generated'') множеством частичных ребер.

В этом примере <tex>H</tex> и <tex>G</tex> эквивалентны, <tex>H \equiv G</tex>{{Определение|definition='''Блоком''' (англ. ''block'') уменьшенного гиперграфа называется связное, и двойственные строго изоморфны: <tex>H^* \cong G^*</tex>вершинно - порожденное множество частичных ребер без сочленения.}}

{{Определение|definition==Ацикличность==Множество частичных ребер называется '''тривиальным''' (англ. ''trivial''), если оно содержит одно гиперребро.}}

В отличие от обычных неориентированных графов{{Определение|definition=Уменьшенный гиперграф называется '''<tex> \alpha </tex> - ацикличным''' (англ. ''<tex> \alpha </tex>-acyclity'') , для которых существует только одно понятие ацикличностиесли всего его блоки тривиальны, существует множество неэквивалентных определений ацикличности гиперграфовиначе называют '''<tex> \alpha </tex>-цикличным''' (англ. ''<tex> \alpha</tex>-cyclity'').}}

Первое определение ацикличности для гиперграфов было дано Клаудом Бержем: гиперграф называется ацикличным по Бержу, если инцидентный ему граф ацикличный. Это определение достаточно ограничено. Например, если гиперграф имеет какую-то пару вершин <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> [[Файл:Alpha-acyclity- ацикличность1. Это понятие ацикличности эквивалентно определению гиперграфа, который является конформальным(тpng|thumb|left|500px|Рис.е. каждая клика исходного графа покрыта каким-то гиперребром), и при этом исходный граф является хордальным ; это также эквивалентно сводимости пустого графа через GYO алгоритм(более известный как алгоритм Грэхема), повторяющийся процесс, который удаляет гиперребра с использованием главного определения "ухо графа". В области теории баз данных известно, что схема баз данных обладает некоторыми желательными свойствами, если ее основной граф является 5: <tex>\alpha</tex> - ациклическимацикличный гиперграф]][[Файл:Alpha-acyclity-2.png|thumb|center|500px|Рис. 6: Подмножество гиперребер <tex>\alpha{ 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>dгиперграф не будет связным (vвершина <tex>B</tex> не будет ни с кем соединена). Заметим, что на рис. 6 подмножетсво гиперребер <tex>\{ ABC, CDE, EFA \}</tex> не имеет сочленения. Однако, это множество не является вершинно - порожденным , таким образом, нет никаких противоречий с предположением, что гиперграф на рис. 5 является <tex> \alpha </tex>-ацикличным.  Заметим, что <tex> \alpha </tex> -ацикличность имеет одно нелогичное свойство: при добавлении гиперребер к <tex> \alpha </tex>-цикличному гиперграфу он может стать <tex> \alpha </tex>-ацикличным (например, при добавлении гиперребра, которое охватывает все вершины , всегда будет делать гиперграф <tex>v\alpha </tex> называется число гиперребер-ацикличным). Из-за этого свойства было введено более строгое определение, которые содержат называемое <tex>v\beta </tex>-ацикличностью.  {{Определение|definition=Гиперграф <tex>H= (V, E) </tex> называетсяявляется '''<tex>k\beta </tex>- регулярнымацикличным'''(англ. ''<tex> \beta </tex>-acyclity'') , если каждая вершина имеет степень все его подгиперграфы <tex> \alpha </tex>-ацикличны.}} Так например гиперграф на рис. 5 является <tex> \alpha </tex>-ацикличным, но не является <tex> \beta </tex>-ацикличным, так как его подгиперграф на рис. 6 является <tex>k\alpha </tex>-цикличным. == См.также ==* [[Основные_определения_теории_графов|Основные определения теории графов]]

Две вершины <tex>x<== Источники информации ==* [https://en.wikipedia.org/wiki/Claude_Berge wikipedia.com — Клауд Берж]* [https://en.wikipedia.org/tex> и <tex>y<wiki/tex> гиперграфа <tex>H<Hypergraph wikipedia.com — Гиперграфы]* [http:/tex> называются симметричными, если существует такой автоморфизм, что <tex>w(x) = y</tex>www. Тва ребра <tex>e_i<sciencedirect.com/science/article/tex> и <tex>e_j<pii/tex> называются симметричными, если существет такой автоморфизм, что <tex>w(e_i) S0012365X09003446?np= e_j</tex>y sciencedirect.com — Ацикличность в гиперграфах]

Гиперграф называется '''вершинно-транзитивным'''(или '''вершинно-симметричным'''), если все вершины симметричны. Точно так же, гиперграф называется '''реберно-транзитивным'''6 если все его ребра симметричны. Если гиперграф [[Категория:Дискретная математика и вершинно-тразитивный, и реберно-транзитивный , тогда гиперграф называется '''транзитивным'''.алгоритмы]][[Категория:Основные определения теории графов]]