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

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

Exempel

För alla k kallas K 1 , k {\displaystyle K_{1,k}} för stjärngrafer. I bilden syns K 1 , 3 , K 1 , 4 , K 1 , 5 , K 1 , 6 {\displaystyle K_{1,3},K_{1,4},K_{1,5},K_{1,6}} .
  • '"`UNIQ--postMath-0000000B-QINU`"'
    K 1 , 1 {\displaystyle K_{1,1}}
  • '"`UNIQ--postMath-0000000C-QINU`"'
    K 2 , 2 {\displaystyle K_{2,2}}
  • '"`UNIQ--postMath-0000000D-QINU`"'
    K 3 , 2 {\displaystyle K_{3,2}}
  • '"`UNIQ--postMath-0000000E-QINU`"'
    K 3 , 3 {\displaystyle K_{3,3}}

Egenskaper

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

Referenser

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