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.
jest zbiorem krawędzi hipergrafu, czyli podzbioremzbioruP(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
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
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 zachodzi twierdzenie:
Przykładowa macierz hipergrafu dualnego do hipergrafu