Graf bipartit

Exemple de graf bipartit.

Un graf bipartit és en teoria de grafs un graf no dirigit els vèrtexs del qual es poden separar en dos conjunts disjunts $V_{1}$ i $V_{2}$ i les arestes sempre uneixen vèrtexs d'un conjunt amb vèrtexs d'un altre:

* $V_{1}\cup V_{2}=V$

* $V_{1}\cap V_{2}=\emptyset$

* $\forall x_{1},x_{2}\in V_{1},\forall y_{1},y_{2}\in V_{2}$ no hi ha cap aresta $i={x_{1},x_{2}}$ ni $i={y_{1},y_{2}}$

Sent $V$ el conjunt que conté tots els vèrtexs del graf.

Els grafs bipartits solen representar gràficament amb dues columnes (o files) de vèrtexs i les arestes unint vèrtexs de columnes (o files) diferents.

Els dos conjunts U i V poden ser pensats com un acolorit del graf amb dos colors: si vam pintar els vèrtexs de U de blau i els vèrtexs de V de verd obtenim un graf de dos colors on cada aresta té un vèrtex blau i l'altre verd. D'altra banda, si un gràfic no té la propietat que es pot pintar amb dos colors no és bipartit.

Un graf bipartit sol amb la partició dels vèrtexs en U i V sol denotar G = (U, V, L). Si |U|=|V|, és a dir, si els dos subconjunts té la mateixa quantitat d'elements, diem que el graf bipartit G és balancejat.

Exemples

• Tot graf sense cicles amb quantitat de nodes senar és bipartit. Per tant:
  • Tot arbre és bipartit.
  • Els grafs cíclics amb un nombre parell de vèrtexs són bipartits.
  • Tot graf planar on totes les cares tenen un nombre parell d'arestes és bipartit.

Vegeu també

• Graf bipartit complet