Grafo bipartito

Grafo bipartito

Eixemple de grafo bipartito.

Grafo bipartito en un subconjunt V1 i un atre V2

Erro al crear miniatura:

Grafo bipartito complet

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

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

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.

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\cup V=N$ i $U\cap V=\mathrm{\varnothing }$, de manera que les arestes només poden conectar vèrtiços d'un conjunt en vèrtiços de l'atre; formalment: $\mathrm{\forall }{u}_1,u_2\in U,\mathrm{\forall }{v}_1,v_2\in V$ no existix cap aresta $e=(u_1,u_2)$ ni $e=(v_1,v_2)$.

Representació

Els grafos bipartitos 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 bipartito 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 bipartito 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é

• Grafo bipartito complet

Bibliografia

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