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{array}{cccccc}1& 1& 0& 0& 0& 1\\ 0& 1& 1& 1& 0& 0\\ 0& 0& 0& 0& 1& 1\end{array}\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{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 0& 1& 0\\ 0& 1& 0\\ 0& 0& 1\\ 1& 0& 1\end{array}\right]$

Bibliografia

• Szablon:Cytuj książkę