HERNANDO GONZALEZ VALENCIANO
ESPECIALIZACION II: GRAFO BIPARTITO

domingo, 17 de febrero de 2008

GRAFO BIPARTITO

Un Grafo bipartito se denomina en Teoría de grafos a un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen vértices de un conjunto con vértices de otro:

  • V_1 \cup V_2 = V
  • V_1 \cap V_2 = \empty
  • \forall x_1,x_2 \in V_1, \forall y_1,y_2 \in V_2 no existe ninguna arista e = (x1,x2) ni e = (y1,y2)
Grafo bipartito completo K2,3
Grafo bipartito completo K2,3

Siendo V el conjunto que contiene todos los vértices del grafo.

El conjunto de todos los grafos bipartitos es denominado {K}^{\left [2\right ]}; en particular, un grafo bipartito uniendo dos conjuntos, de m y n elementos, respectivamente, se denota por {K}^{\left [2\right ]}_{m,n}, o, simplemente, Km,n.

Un grafo bipartito en el cual todos los elementos de V1 están unidos con todos los elementos de V2 se denomina bipartito completo

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

Un árbol.

Un grafo sin ciclos de tamaño impar.