Hypergraf

Från Wikipedia
Hoppa till: navigering, sök
En hypergraf med nodmängden ,och bågmängden .

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

Definition[redigera | redigera wikitext]

En hypergraf är ett par där är en mängd element och är en mängd av icke-tomma delmängder av , så att .

Som bipartita grafer[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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