Hypergraf

Från Wikipedia
Hoppa till: navigering, sök
En hypergraf med nodmängden 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\}\}.

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 (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[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