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

Om ${\displaystyle V_{1}}$ har storlek m och ${\displaystyle V_{2}}$ har storlek n brukar G betecknas ${\displaystyle K_{m,n}}$

Exempel

• 

  ${\displaystyle K_{1,1}}$

• 

  ${\displaystyle K_{2,2}}$

• 

  ${\displaystyle K_{3,2}}$

• 

  ${\displaystyle K_{3,3}}$

Egenskaper

• ${\displaystyle K_{m,n}}$ har en maximal oberoende mängd med storlek ${\displaystyle \max(n,m)}$.
• Grannmatrisen till ${\displaystyle K_{m,n}}$ har egenvärdena ${\displaystyle {\sqrt {mn}},-{\sqrt {mn}}}$ och 0 med multipliciteterna 1, 1 och ${\displaystyle n+m-2}$ respektive.
• ${\displaystyle K_{m,n}}$ har ${\displaystyle m^{n-1}n^{m-1}}$ uppspännande träd.
• ${\displaystyle K_{n,n}}$ och ${\displaystyle K_{n,n+1}}$ är Turángrafer.

Referenser

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