Verificador de Grafo Bipartito

Pseudocódigo

Un grafo es bipartito exactamente cuando puede colorearse con dos colores. Así que la prueba es un recorrido que colorea cada vértice del color opuesto a su padre y vigila si aparece un choque.

esBipartito(grafo):
    color = {} para todos los vértices

    para cada vértice s sin color:    // cada componente
        color[s] = 0
        cola = [s]
        mientras la cola no esté vacía:
            u = cola.sacar()
            para cada vecino v de u:
                si v no tiene color:
                    color[v] = 1 - color[u]
                    cola.meter(v)
                si no, si color[v] == color[u]:
                    devolver falso   // ciclo impar

    devolver verdadero

El choque no es una señal arbitraria de fallo, es una demostración. Si dos vértices adyacentes reciben el mismo color, los caminos del árbol desde ambos hasta su antecesor común más la arista que los conecta forman un ciclo de longitud impar. Los grafos bipartitos son exactamente los grafos sin ciclos impares, así que la arista en conflicto es un certificado que puedes devolver al llamante.

Ejemplo resuelto, paso a paso

Colorea con dos colores un ciclo de cuatro vértices, después añade una cuerda y observa cómo el mismo recorrido lo rechaza.

Grafo de ejemplo: Primero un ciclo de 4 con A-B, B-C, C-D, D-A. Después el mismo grafo con la cuerda A-C añadida.

1. Colorear el ciclo de 4 desde A. A recibe el color 0. Sus vecinos B y D reciben el color 1. Desde B, el vecino C no tiene color y recibe el 0. Desde D, el vecino C ya está coloreado con 0 mientras que D es 1, lo cual es una diferencia válida, así que nada entra en conflicto.
2. Resultado para el ciclo de 4. Los colores son A 0, B 1, C 0, D 1. El grafo es bipartito, con las partes {A, C} y {B, D}. Toda arista va entre las dos partes y ninguna queda dentro de una de ellas.
3. Añadir la cuerda A-C. A y C tienen ambos el color 0, así que la cuerda une ahora dos vértices de la misma parte. Vuelve a ejecutar el recorrido desde A: A recibe 0, y sus vecinos B, D y ahora C reciben todos el 1.
4. Aflora el conflicto. Al procesar B, cuyo color es 1, su vecino C tiene también el color 1. Eso es una arista dentro de una misma parte, así que el algoritmo devuelve falso en la arista B-C.
5. Por qué la cuerda lo rompe. La cuerda crea el triángulo A-B-C, un ciclo de longitud 3. Los ciclos impares no pueden colorearse con dos colores: recorrer un ciclo impar alternando colores te devuelve al inicio necesitando el opuesto del que ya tiene.

El ciclo de 4 es bipartito con las partes {A, C} y {B, D}; añadir la cuerda A-C lo hace no bipartito, y se detecta en la arista B-C. Fíjate en la regla general que ilustra: todo ciclo par es bipartito y todo ciclo impar no lo es, así que la longitud del ciclo por sí sola lo decide. Fíjate también en que el conflicto se informó en la arista B-C y no en la propia cuerda, lo cual es normal, ya que el algoritmo informa donde la contradicción aflora primero, no donde tú echarías la culpa.

Complejidad y de dónde sale

Tiempo: O(V + E) · Espacio: O(V)

Esto es un único BFS o DFS con una comparación por arista, así que cuesta exactamente un recorrido. Cada vértice se colorea una vez y cada arista se inspecciona una vez desde cada extremo. El espacio es un color por vértice más la cola o la pila de recursión, ambos O(V). El bucle sobre todos los vértices no añade nada asintóticamente y es lo que hace que funcionen los grafos desconectados. No hay ningún enfoque más rápido, ya que decidir la bipartición requiere mirar cada arista: una sola arista sin examinar podría ser la que crea un ciclo impar.

Cuándo usar Comprobación de Grafo Bipartito y cuándo no

La bipartición suele ser una condición previa más que un objetivo. Lo que hagas después depende de por qué preguntaste.

Errores frecuentes

• Recorrer solo desde un vértice. Un grafo desconectado es bipartito solo si lo es cada componente. Arrancar desde un único origen prueba una componente y deja pasar en silencio un grafo que contiene un ciclo impar en otra parte. Recorre todos los vértices y arranca un recorrido nuevo desde cada uno sin colorear.
• Tratar sin color como si fuera un color. Usar 0 tanto para no visitado como para la parte cero hace que la comprobación de conflicto falle. Usa un centinela aparte, como -1 o la ausencia en un mapa, de modo que sin color todavía y color 0 sean distinguibles.
• Olvidar que los bucles propios son fatales. Un bucle propio es un ciclo impar de longitud 1 y hace que un grafo no sea bipartito de inmediato. Un recorrido que salta al padre puede pasarlo por alto por completo, así que compruébalos explícitamente.
• Suponer que el caso interesante es acíclico implica bipartito. Todo árbol y todo bosque es trivialmente bipartito, ya que no tiene ciclos en absoluto. La prueba solo cobra sentido cuando existen ciclos, de modo que los aprobados triviales sobre entradas con forma de árbol demuestran muy poco.
• Aplicarlo a grafos dirigidos sin simetrizar. La bipartición es una propiedad no dirigida. En un grafo dirigido has de decidir si una arista de un solo sentido cuenta como adyacencia y tratar las aristas de forma simétrica, o la respuesta no está bien definida.

Preguntas frecuentes

¿Qué es un grafo bipartito?

Un grafo bipartito es aquel cuyos vértices pueden dividirse en dos conjuntos de modo que toda arista une un vértice de uno con un vértice del otro, sin aristas dentro de ninguno de los dos. Equivalentemente, es un grafo que puede colorearse correctamente con dos colores y, otra vez equivalentemente, un grafo que no contiene ningún ciclo de longitud impar.

¿Cómo se comprueba si un grafo es bipartito?

Ejecuta un BFS o un DFS coloreando cada vértice recién alcanzado con el color opuesto al del vértice desde el que llegaste. Si alguna vez encuentras una arista cuyos dos extremos ya comparten color, el grafo no es bipartito. Repite desde cada vértice sin colorear para cubrir todas las componentes. Toda la prueba es O(V + E).

¿Por qué los ciclos impares son el factor decisivo?

Porque los colores deben alternarse a lo largo de cualquier camino. Recorrer un ciclo de longitud par te devuelve al inicio con el color con el que empezaste, lo cual es consistente. Recorrer un ciclo impar te devuelve necesitando el color opuesto al ya asignado, lo cual es una contradicción. Así que un grafo es bipartito exactamente cuando no tiene ciclos impares.

¿Cuál es la complejidad temporal de comprobar la bipartición?

O(V + E) en tiempo y O(V) en espacio. Es un único recorrido con una comparación de color por arista. Es óptimo, porque cualquier arista sin examinar podría ser la que crea un ciclo impar, así que hay que mirarlas todas.

¿Para qué se usan los grafos bipartitos?

Para modelar cualquier relación de dos lados: candidatos y puestos, estudiantes y asignaturas, compradores y vendedores, documentos y términos. Una vez que se sabe que un grafo es bipartito, el emparejamiento máximo pasa a ser eficientemente resoluble mediante Hopcroft-Karp, lo que sustenta problemas de asignación, planificación y sistemas de recomendación.