Graf bipartit complet

En teoria de grafs un graf bipartit complet és aquell graf bipartit en el qual tots els vèrtexs de la partició $V_1$ estan connectats a tots els vèrtexs de la partició $V_2$ i viceversa.

Definició

Un graf bipartit complet $G:=(V_1\cup V_2,E)$ és un graf bipartit tal que $\mathrm{\forall }{v}_1\in V_1,\mathrm{\forall }{v}_2\in V_2\to i(v_1,v_2)\in E.$ És a dir, un graf bipartit complet està format per dos conjunts disjunts de vèrtexs i totes les possibles arestes que uneixen aquests vèrtexs.

El graf complet bipartit amb particions de mida $\left|V_1\right|=m$ i $\left|V_2\right|=n,$ és denotat com $K_{m,n}$.

Exemples

• 
  K_3,1
• 
  K_3,2
• 
  K_3,3

Propietats

• Sigui $K_{m,n}$ un graf bipartit amb $\left|V_1\right|=m$ i $\left|V_2\right|=n$, es verifica que $\left|E\right|=\left|V_1\right|\cdot \left|V_2\right|=m\cdot n$ i $K_{m,n}$ posseeix $m^{n-1}\cdot n^{m-1}$ arbres d'expansió.
• Donat un graf bipartit, comprovar si conté un subgraf bipartit complet $K_{i,i}$ per un paràmetre $i$ és un problema NP-complet.
• Un graf planar no pot contenir K_3,3 com a subconjunt, i un graf planar exterior (sense vèrtexs interns) no pot contenir K_3,2 com a subconjunt. (No són condicions suficients per a la planaritat i la planaritat exterior, però són necessàries). D'altra banda, segons el teorema de Wagner, tot graf no planar conté K_3,3 o bé el graf complet K₅ com a subconjunts.
• Tot graf bipartit complet de la forma $K_{i,i}$ és un graf de Moore.
• Tot graf bipartit complet és un graf modular, és a dir, cada triplet de vèrtexs té una mediana que pertany als camins més curts entre cada parell possible d'aquests vèrtexs.

Bibliografia

• Plantilla:Ref-llibre (Electronic edition).

Vegeu també

• Graf bipartit
• Graf complet