44
правки
Изменения
sta
В математике '''Гиперграфомгиперграф''' (англ. ''hypergraph'') называется - это обобщение графа, в котором каждое ребро соединяет необязательно две вершиныу которого ребра могут соединять любое количество вершин. ФормальноБолее формально, '''гиперграф''' {{--<tex>H</tex> -}} упорядоченная это пара <tex>H = (VX,E)</tex>, где <tex>VX</tex> {{---}} множество вершин гиперграфаэлементов называемых узлами или вершинами, а и <tex>E</tex> {{---}} множество ребер гиперграфа, где каждое ребро является подмножеством множества вершинне пустое подмножество <tex>X</tex> называемых гиперребрами или просто ребрами.
В дальнейшем будем считатьто время, что все рассматриваемые гипергафы обладают свойствами: *как ребра графа соединяют две пары вершин, гиперребра - произвольные множества вершин, которые могут содержать любое количество вершин. Однако, очень часто рассматривают гиперграфы с гиперребрами одинаковой мощности ; <tex>\forall ik</tex> - равномерный гиперграф - это такой гиперграф, у которого все гиперребра имеют размер k. (Другими словами, такой гиперграф множество подмножеств, которые содержат k вершин). Так например, <tex> E_i \neq \emptyset </tex> *<tex> \cup E = X 2</tex>- равномерный гиперграф - обычный граф.
[[Файл:Hypergraph.jpg|right|thumb|Частный случай гипергафа, где <tex>E=\{e_1, e_2, e_3, e_4\} = \{\{v_1, v_2, v_3\}, \{v_2,v_3\}, \{v_3,v_5.v_6\}, \{v_4\}\}</tex>]]
==Определения==
Так как множество гиперребер может быть любой мощности, существуют несколько понятий '''подграфа''' гиперграфа, называемых '''подгиперграфами''', '''частичные гиперграфы''Подгиперграфом'и '' (англ. 'разрез гиперграфов'subhypergraph''. Пусть <tex>H = (X, E) </tex>H_1- гиперграф содержащий множество вершин <tex>X = \{x_i | i \in I_v\}</tex> гиперграфа и множество ребер <tex>HE =(V\{e_i | i \in I_e, e_i \subseteq X\}</tex>, где <tex>I_v</tex> и <tex>I_e</tex> множества индексов вершин и ребер соответсвенно.
'''Подгиперграфом''' называют гиперграф с некоторым множеством удаленных вершин. Формально, подгиперграф <tex>H_a</tex> ,E)индуцированный подмножеством <tex>A</tex> множества <tex> X </tex> назывется гипергаф: , который определен как
<tex>H_1 H_a = (V_1A, \{E_1 e_i \cap A| \forall i: e_i \cap V_1 A \neq \emptyset \}).</tex> '''Частичным''' гипергафом называется гиперграф, с множеством удаленных ребер. ИначеДанное подмножество <tex>J \subset I_e </tex> множества индексов ребер, подгипергаф частичный граф сгенерирован с помощью <tex>J</tex>, т.е <tex>(X, \{ e_i | i \in J \}).</tex> Пусть дано множество <tex>A \subseteq X</tex>, разрезом гиперграфа называют такой '''частичный''' гиперграф <tex>
H \times A = (A, \{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 | x_m \in e_i \} это гипергаф с некоторомы удаленными вершинами.</tex> Когда операция равенства определена, как показано ниже, операция взятия '''двойственного''' гиперграфа выглядит следующим образом
<tex>(H*)* = H.</tex>
==АцикличностьИзоморфность и эквивалентсность==ЗаметимГиперграф <tex>H = (X, E)</tex> изоморфен гиперграфу <tex>G = (Y, F)</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 \equiv G</tex> тогда и только тогда, когда <tex>H* \simeq G</tex>*
