Anar al contingut

Grafo bipartit

De L'Enciclopèdia, la wikipedia en valencià
Grafo bipartit
Eixemple de grafo bipartit.
Grafo bipartit en un subconjunt V1 i un atre V2
Erro al crear miniatura:
Grafo bipartit complet

En teoria de grafos, un grafo bipartit és un grafo que els seus vèrtiços es poden separar en dos conjunts disjunts, de manera que les arestes no poden relacionar vèrtiços d'un mateix conjunt.[1]

Un grafo bipartit complet és un grafo bipartit en que tots els vèrtiços d'un dels subconjunts estan relacionats en els de l'atre subconjunt.[1]

Este concepte es pot generalisar al de grafo s-partito, com un grafo el conjunt del qual de vèrtiços es pot particionar en s subconjunts, de modo que les arestes solament conecten a vèrtiços de subconjunts diferents. Análogamente, també es pot definir un grafo s-partito complet, com un en que tots els parells de vèrtiços pertanyents a subconjunts diferents són adjacents.[1]

Definició formal

Un grafo G=(N,E) és bipartito si N es pot particionar en dos conjunts O i V, és dir, tal que U∪V=N i U∩V=∅, de manera que les arestes només poden conectar vèrtiços d'un conjunt en vèrtiços de l'atre; formalment: ∀u1,u2∈U,∀v1,v2∈V no existix cap aresta e=(u1,u2) ni e=(v1,v2).

Representació

Els grafos bipartits solen representar-se gràficament en dos columnes (o files) de vèrtiços i les arestes unint vèrtiços de columnes (o files) diferents.

Els dos conjunts O i V poden ser pensats com un coloreo del grafo en dos colors: si pintem els vèrtiços en O de blau i els vèrtiços de V de vert obtenim un grafo de dos colors a on cada aresta té un vèrtiç blau i l'atre vert. Per un atre costat, si un grafo no té la propietat de que es pot colorear en dos colors no és bipartito.

Un grafo bipartit en la partició dels vèrtiços en O i V sol denotar-se G = (O, V, I). Si |O| =|V|, açò és, si els dos subconjunts té la mateixa cantitat d'elements o cardinalidad, diem que el grafo bipartit G és balancejat. Si tots els vèrtiços del mateix costat de la bipartición tenen el mateix grau, llavors G és cridat grafo birregular.

Vore també

Referències

  1. ↑ 1,0 1,1 1,2 Wasserman y Faust, 2013, «Grafos i matrius» (per Dawn Iacobucci), pp. 121-188.

Bibliografia

  • Wasserman, Stanley; Faust, Katherine (2013). Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.