Hipergraf

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”^[1], 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: