Diferència entre revisions de la pàgina «Graf bipartit»

4 octets eliminats ,  fa 6 anys
m
neteja, redactat
(Robot estandarditza i catalanitza referències, catalanitza dates i fa altres canvis menors)
m (neteja, redactat)
Etiquetes: Edita des de mòbil Edició web per a mòbils
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 acoloreixacolorit del graf amb dos colors: si vam pintar els vèrtexs ende U de blau i els Vericarvè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 ==