¿Cómo saber si un grafo es bipartito?

Question

S o

Tengo dibujados los siguientes gráficos. ¿Cómo puedo saber si son bipartitos? Si es bipartito, ¿cómo identificar 2 conjuntos no vacíos disjuntos?

Answer 1

Utiliza el algoritmo de coloración de vértices:

1) Colorea de rojo cualquiera de tus vértices.

2) Identifica todos los vértices no coloreados que son adyacentes a un vértice rojo. Coloréalos de azul.

3) Identifica todos los vértices no coloreados que son adyacentes a un vértice azul. Coloréalos de rojo.

4) Repite los pasos 2 y 3 hasta que todos los vértices estén coloreados en rojo o azul.

5) Si hay dos vértices adyacentes del mismo color, entonces tu grafo no es bipartito, en caso contrario es bipartito.

6) Si el grafo es bipartito, el algoritmo de coloreado habrá creado los dos conjuntos de puntos necesarios (uno rojo y otro azul).

Answer 2

Una forma rápida de ver que el gráfico (b) no puede ser bipartito es observar que tiene un triángulo. ¿Por qué es un problema? Bueno, los grafos bipartitos son precisamente la clase de grafos que son 2-colorables. Recordemos que una coloración es una asignación de colores a los vértices del grafo de forma que no haya dos vértices adyacentes que reciban el mismo color. Por tanto, si puedes colorear tu grafo de dos colores, será bipartito. Claramente, si tienes un triángulo, necesitas 3 colores para colorearlo.

Cuando tienes una bicoloración, las dos clases de color (vértices rojos, vértices azules), te dan la bipartición.

Answer 3

Un grafo es bipartito si y sólo si existe no existe un ciclo impar dentro del grafo. Supongamos que el grafo en b) es bipartito, es decir, que existen dos conjuntos no vacíos disjuntos $A$ y $B$ . Considere el ciclo $v_2,v_4,v_5$ . Sea $v_2$ estar en $A$ . Desde $v_2$ es adyacente a $v_4$ , $v_4$ debe estar en $B$ . Pero $v_5$ es adyacente a ambos $v_2$ y $v_4$ por lo que no puede estar en ninguno de los dos $A$ o $B$ . Por lo tanto, el grafo no es bipartito.