Grafo bipartido

Grafo bipartido Concepto: Grafo simple sin lazos de forma G=<V1 U V2,A> donde V1 y V2 forman una partición de V tal que todas las aristas tienen su origen en V1 y terminan en V2

Grafo bipartido. Dícese de todo grafo simple sin lazos cuyo conjunto de vértices puede dividirse en dos subconjuntos disjuntos no vacíos de manera que los vértices que los componen solo tengan aristas o arcos con vértices del otro subconjunto, nunca con ningún vértice del mismo conjunto.

Definición.

Un grafo G=<V,A> se dice bipartido o bipartito si y solo si existe una partición de V=V₁ U V₂ tal que para toda arista (x,y) de A se cumple que x es un vertice de V₁ e y está en V₂ o simplemente que A será un subconjunto no nulo de V₁xV₂.

Cuando A=V₁xV₂ se dice que el grafo es bipartido completo.

Ejemplos.

• El grafo bipartido trivial es K₂.

• G=<{a,b}U{c,d,e}, {(a,c),(b,d),(b,e}> es bipartito:

• Un de los grafos de Kuratowvski, K_3,3 es bipartido.

• Todos los K_n,m son bipartidos.

Fuentes.

1. K. Ribnikov. Análisis Combinatorio. Editorial Mir. Moscú, 1988. Páginas 17-23.
2. Artículo:Grafo bipartito en Wikipedia.Disponible en "es.wikipedia.org". Consultado 29 de noviembre de 2011.