Hypergraf

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

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

Definition

En hypergraf är ett par ( X , E ) {\displaystyle (X,E)} där X {\displaystyle X} är en mängd element och E {\displaystyle E} är en mängd av icke-tomma delmängder av X {\displaystyle X} , så att E ⊂ P ( X ) ∖ { ∅ } {\displaystyle 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