- 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:
-
- no existe ninguna arista e = x1,x2 ni e = y1,y2
Siendo V el conjunto que contiene todos los vértices del grafo.
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.
Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul y los vértices deV de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.
Un grafo bipartito suele con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| =|V|, esto es, si los dos subconjuntos tiene la misma cantidad de elementos, decimos que el grafo bipartito G es balanceado.
Ejemplos
- Todo grafo sin ciclos con cantidad de nodos impar es bipartito. Como consecuencia de esto:
- Todo árbol es bipartito.
- Los grafos cíclicos con un número par de vértices son bipartitos.
- Todo grafo planar donde todas las caras tienen un número par de aristas es bipartito.
Véase también
Categoría:- Familias de grafos
-
Wikimedia foundation. 2010.