Komplett bipartit graf

Från Wikipedia
Hoppa till: navigering, sök

En komplett bipartit graf är inom grafteori en särskild bipartit graf där varje nod i ena nodmängden är ansluten till alla noder i den andra nodmängden.

Definition[redigera | redigera wikitext]

En komplett bipartit graf G = (V_1 \cup V_2, E) är en graf sådan att det inte finns några bågar mellan två noder om båda noderna ligger i samma nodmängd, V_1 eller V_2 (grafen är bipartit), men om två noder u och v ligger i varsin nodmängd, V_1 respektive V_2, så är bågen uv ett element i E.

Om V_1 har storlek m och V_2 har storlek n brukar G betecknas K_{m,n}

Exempel[redigera | redigera wikitext]

För alla k kallas K_{1,k} för stjärngrafer. I bilden syns K_{1,3}, K_{1,4}, K_{1,5}, K_{1,6}.

Egenskaper[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]

  • Diestel, Reinhard (2005). Graph Theory. Springer Verlag