Revisió del 22:35, 2 juny 2013 modifica 87.223.45.231 (discussió) Hi havia faltes de coherència. ← Edició anterior		Revisió del 21:20, 25 gen 2015 modifica desfés Bestiasonica (discussió \| contribucions) 244.771 edits mCap resum de modificació Edició següent →
Línia 1: [[fitxer: Simple-bipartite-graph.svg\|200px\|thumb\|Exemple de graf bipartit.]] Un ''' ~~Graf~~graf bipartit ''' ~~s'anomena~~és en [[~~Teoria~~teoria de grafs]] ~~com~~ un [[Graf (matemàtiques)\|graf]] '' no dirigit '' els [[~~Vértice (Teoria de grafs)~~vèrtex\|vèrtexs]] del qual es poden separar en dos [[conjunts disjunts]] <math> V_1 </math> i <math> V_2 </math> i les arestes sempre uneixen vèrtexs d'un conjunt amb vèrtexs d'un altre:▼ ▲Un ''' Graf bipartit ''' s'anomena en [[Teoria de grafs]] com un [[graf]] '' no dirigit '' els [[Vértice (Teoria de grafs)\|vèrtexs]] del qual es poden separar en dos [[conjunts disjunts]] <math> V_1 </math> i <math> V_2 </math> i les arestes sempre uneixen vèrtexs d'un conjunt amb vèrtexs d'un altre: : * <math> V_1 \cup V_2 = V </math> : * <math> V_1 \cap V_2 = \empty </math> : * <math> \forall x_1, x_2 \in V_1, \forall y_1, y_2 \in V_2 </math> no hi ha cap [[~~Arista (Teoria de grafs)\|~~aresta]] <math> i ={x_1, x_2}</math> ni <math> i ={y_1, y_2}</math> Sent <math> V </math> el conjunt que conté tots els vèrtexs del graf. Linha 13 ⟶ 10: 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 == * Tot graf sense cicles amb quantitat de nodes senar és bipartit. Per tant: Tot [[Arbre (teoria de grafs)\|arbre]] és bipartit. Els [[Graf ~~cicle~~cíclic\|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é == * [[Graf bipartit complet]] {{Commonscat}} {{ORDENA:Graf Bipartit}} ~~<!--ORDENA generat per bot-->~~ [[Categoria:Famílies de grafs]]

Graf bipartit: diferència entre les revisions