Hypergraf

En hypergraf är, inom grafteori, en generalisering av en graf, vars bågar kan binda samman ett godtyckligt antal noder.

En hypergraf med nodmängden $X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}$, och bågmängden ${\begin{aligned}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}\}\}\end{aligned}}$.

Definition

En hypergraf är ett par $(X,E)$ där $X$ är en mängd element och $E$ är en mängd av icke-tomma delmängder av $X$, så att $E\subset {\mathcal {P}}(X)\backslash \{\emptyset \}$.

Som bipartita grafer

Hypergrafer kan representeras som vanliga bipartita grafer, då noderna i en hypergrafen bildar en klass av noder och hyperbågarna bildar den andra klassen. En nod n har då en båge till noden b i den bipartita grafen om a som nod i hypergrafen ligger i hyperbågen b.

Referenser

• Berge, Claude (1989). Hypergraphs, Combinatorics of Finite Sets. North-Holland 
• Bollobás, Béla (2002). Modern Graph Theory. Springer Verlag. ISBN 978-0387984889