Hipergraf

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Przykładowy hipergraf H_1.

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

Pojęcie hipergrafu pojawiło się drugiej w 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[edytuj | edytuj kod]

Hipergraf[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 prawdziwe jest twierdzenie, że \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]

Przypisy

  1. patrz Claude Berge w bibliografii

Bibliografia[edytuj | edytuj kod]