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 ${\displaystyle H=(V,E),}$

gdzie:

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

Przykładowy hipergraf ${\displaystyle H_{1}}$ zawiera sześć wierzchołków ${\displaystyle V=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\}}$ oraz trzy hiperkrawędzie: ${\displaystyle E=\{E_{1},E_{2},E_{3}\}.}$ Dwie hiperkrawędzie są incydentne do trzech wierzchołków: ${\displaystyle E_{1}=\{v_{1},v_{2},v_{6}\},}$ ${\displaystyle E_{2}=\{v_{2},v_{3},v_{4}\},}$ natomiast trzecia krawędź jest incydentna do dwóch wierzchołków: ${\displaystyle 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 ${\displaystyle i}$-ta krawędź jest incydentna do ${\displaystyle j}$-tego wierzchołka. W przeciwnym przypadku element ten jest równy 0.

Przykładowa macierz incydencji dla hipergrafu ${\displaystyle H_{1}{:}}$

${\displaystyle 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 ${\displaystyle H=(V,E)}$ istnieje hipergraf dualny ${\displaystyle H^{*}=(E,V),}$ którego krawędzie odpowiadają wierzchołkom hipergrafu ${\displaystyle H,}$ natomiast wierzchołki – krawędziom. Macierz incydencji ${\displaystyle A^{*}}$ hipergrafu dualnego ${\displaystyle H^{*}}$ jest transponowaną macierzą hipergrafu ${\displaystyle H.}$ Analogicznie, macierz ${\displaystyle A}$ jest transponowaną macierzą ${\displaystyle A^{*}.}$ Ponadto zachodzi twierdzenie:

${\displaystyle \left(H^{*}\right)^{*}=H.}$

Przykładowa macierz ${\displaystyle A_{1}^{*}}$ hipergrafu dualnego do hipergrafu ${\displaystyle H_{1}{:}}$

${\displaystyle 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

Bibliografia

• Claude Berge: Graphs and Hypergraphs. Amsterdam: North-Holland, 1973. ISBN 0-444-10399-6. (ang.). Brak numerów stron w książce