Komplett bipartit graf

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

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

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

Egenskaper

  • 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

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

Media som används på denna webbplats

Star graphs.svg
Författare/Upphovsman: Koko90, Licens: CC BY-SA 3.0
Star graphs