Hipergraf

Przykładowy hipergraf $H_{1}.$

Hipergraf – rozszerzenie pojęcia grafu. Jego krawędzie, nazywane hiperkrawędziami, mogą być incydentne do dowolnej liczby wierzchołków.

Pojęcie hipergrafu pojawiło się w drugiej połowie ubiegłego stulecia. W 1973 roku francuski matematyk Claude Berge opublikował monografię „Grafy i hipergrafy”, w której sformalizował oraz ujednolicił podstawowe definicje dotyczące teorii hipergrafów.

Definicje

Hipergraf

Hipergraf definiuje uporządkowana para $H=(V,E),$

gdzie:

• $V$ jest dowolnym, niepustym zbiorem wierzchołków;
• $E$ jest zbiorem krawędzi hipergrafu, czyli podzbiorem zbioru P(V) wszystkich możliwych niepustych zbiorów, których elementy należą do $V.$

Przykładowy hipergraf $H_{1}$ zawiera sześć wierzchołków $V=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\}$ oraz trzy hiperkrawędzie: $E=\{E_{1},E_{2},E_{3}\}.$ Dwie hiperkrawędzie są incydentne do trzech wierzchołków: $E_{1}=\{v_{1},v_{2},v_{6}\},$ $E_{2}=\{v_{2},v_{3},v_{4}\},$ natomiast trzecia krawędź jest incydentna do dwóch wierzchołków: $E_{3}=\{v_{5},v_{6}\}.$

Macierz incydencji

Macierz incydencji, jest jedną z najpopularniejszych i najwygodniejszych metod reprezentacji hipergrafu. W macierzy incydencji wiersze odpowiadają krawędziom, a kolumny wierzchołkom hipergrafu. Jeśli element macierzy jest równy 1, to $i$-ta krawędź jest incydentna do $j$-tego wierzchołka. W przeciwnym przypadku element ten jest równy 0.

Przykładowa macierz incydencji dla hipergrafu $H_{1}{:}$

$A_{1}=\left[{\begin{matrix}1&1&0&0&0&1\\0&1&1&1&0&0\\0&0&0&0&1&1\end{matrix}}\right]$

Hipergraf dualny

Dla każdego hipergrafu $H=(V,E)$ istnieje hipergraf dualny $H^{*}=(E,V),$ którego krawędzie odpowiadają wierzchołkom hipergrafu $H,$ natomiast wierzchołki – krawędziom. Macierz incydencji $A^{*}$ hipergrafu dualnego $H^{*}$ jest transponowaną macierzą hipergrafu $H.$ Analogicznie, macierz $A$ jest transponowaną macierzą $A^{*}.$ Ponadto zachodzi twierdzenie:

$\left(H^{*}\right)^{*}=H.$

Przykładowa macierz $A_{1}^{*}$ hipergrafu dualnego do hipergrafu $H_{1}{:}$

$A_{1}^{*}=\left[{\begin{matrix}1&0&0\\1&1&0\\0&1&0\\0&1&0\\0&0&1\\1&0&1\end{matrix}}\right]$

Bibliografia

• Claude Berge: Graphs and Hypergraphs. Amsterdam: North-Holland, 1973. ISBN 0-444-10399-6. (ang.).brak strony w książce