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=V1 U V2 tal que para toda arista (x,y) de A se cumple que x es un vertice de V1 e y está en V2 o simplemente que A será un subconjunto no nulo de V1xV2.

Cuando A=V1xV2 se dice que el grafo es bipartido completo.

Ejemplos.

  • El grafo bipartido trivial es K2.

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

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

  • Todos los Kn,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.
This article is issued from Ecured. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.