Hipergraf

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Przykładowy 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ę 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]

Hipergraf[edytuj]

Hipergraf definiuje uporządkowana para ,

gdzie:

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

Przykładowy hipergraf zawiera sześć wierzchołków oraz trzy hiperkrawędzie: . Dwie hiperkrawędzie są incydentne do trzech wierzchołków: , , natomiast trzecia krawędź jest incydentna do dwóch wierzchołków: .

Macierz incydencji[edytuj]

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 -ta krawędź jest incydentna do -tego wierzchołka. W przeciwnym przypadku element ten jest równy 0.

Przykładowa macierz incydencji dla hipergrafu :

Hipergraf dualny[edytuj]

Dla każdego hipergrafu istnieje hipergraf dualny , którego krawędzie odpowiadają wierzchołkom hipergrafu , natomiast wierzchołki - krawędziom. Macierz incydencji hipergrafu dualnego jest transponowaną macierzą hipergrafu . Analogicznie, macierz jest transponowaną macierzą . Ponadto prawdziwe jest twierdzenie, że .

Przykładowa macierz hipergrafu dualnego do hipergrafu :

Przypisy

  1. patrz Claude Berge w bibliografii

Bibliografia[edytuj]