Hypergraaf

Een hypergraaf is een veralgemeende vorm van een graaf. In een "gewone" graaf verbindt een kant twee knopen; maar in een hypergraaf kan een hyperkant een willekeurig aantal knopen omvatten, gaande van 1 tot het aantal knopen in de graaf.

Een voorbeeld van een hypergraaf met 7 knopen v₁...v₇ en vier kanten: e₁...e₄. $X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}$ en $E=\{e_{1},e_{2},e_{3},e_{4}\}=$ $\{\{v_{1},v_{2},v_{3}\},$ $\{v_{2},v_{3}\},$ $\{v_{3},v_{5},v_{6}\},$ $\{v_{4}\}\}$.

Een hypergraaf kan men beschouwen als een verzameling van deelverzamelingen van een gegeven basisverzameling. Formeel wordt een hypergraaf gedefinieerd als het paar H = (X, E), waarin X de verzameling van knopen is en E de verzameling van (hyper)kanten; elke hyperkant is een niet-lege deelverzameling van X.

De problemen die in de grafentheorie optreden worden ook bestudeerd in hypergrafen, zoals kleuring, kantenbedekking en knopenbedekking, koppelingen, de verdeling van een graaf in cliques, het vinden van een Hamiltonpad of Hamiltoncircuit, enzovoort.

Uniforme hypergrafen

De hypergraaf van het Fano-vlak

In de praktijk bestudeert men vaak hypergrafen waarin alle hyperkanten dezelfde cardinaliteit hebben; die noemt men uniforme hypergrafen. Een k-uniforme hypergraaf heeft hyperkanten met uitsluitend cardinaliteit k; met andere woorden, de verzameling E bestaat uit verzamelingen met k elementen. Een 2-uniforme hypergraaf is dus een "gewone" graaf; een 3-uniforme hypergraaf is een verzameling van drietallen, enz.

De hypergraaf van het Fano-vlak is een voorbeeld van een 3-uniforme hypergraaf. De graaf heeft zeven knopen (genummerd 0 tot 6) en zeven hyperkanten: {5,1,6}, {5,2,3}, {6,4,3}, {1,0,3}, {2,0,6}, {5,0,4} en {1,2,4}.