Graf bipartit

De Viquipèdia
Dreceres ràpides: navegació, cerca
Exemple de graf bipartit.

Un Graf bipartit s'anomena en Teoria de grafs com 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 = \empty
*  \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 acoloreix del graf amb dos colors: si vam pintar els vèrtexs en U de blau i els Vericar 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[modifica | modifica el codi]

  • Tot graf sense cicles amb quantitat de nodes senar és bipartit. Per tant:
    • Tot arbre és bipartit.
    • Els graf 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é[modifica | modifica el codi]


A Wikimedia Commons hi ha contingut multimèdia relatiu a: Graf bipartit Modifica l'enllaç a Wikidata