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 ä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, eller (grafen är bipartit), men om två noder u och v ligger i varsin nodmängd, respektive , så är bågen uv ett element i E.

Om har storlek m och har storlek n brukar G betecknas

Exempel[redigera | redigera wikitext]

För alla k kallas för stjärngrafer. I bilden syns .

Egenskaper[redigera | redigera wikitext]

  • har en maximal oberoende mängd med storlek .
  • Grannmatrisen till har egenvärdena och 0 med multipliciteterna 1, 1 och respektive.
  • har uppspännande träd.
  • och är Turángrafer.

Referenser[redigera | redigera wikitext]

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