Laboratorio: Bipartición y Conectividad Fuerte
Explora cómo las capas de BFS certifican la 2-colorabilidad (o aíslan ciclos impares) y cómo 2 recorridos BFS determinan la conectividad fuerte en digrafos.
Configuración del Grafo
Haz clic en "Ejecutar Prueba" para inspeccionar aristas entre capas contiguas o dentro de la misma capa.
Teorema de Bipartición (BFS):
- Caso (i): No hay aristas entre nodos de la misma capa $\implies G$ es bipartito (capas pares azules, impares blancas).
- Caso (ii): Existe arista $(x, y)$ con $x,y \in L_j \implies$ se forma un ciclo impar de longitud $1 + 2(j-i)$ mediante su $\text{lca}(x,y)$.
Capa par (Azul)
Capa impar (Blanco)
Arista en misma capa (Ciclo impar)
Configuración del Digrafo
Selecciona un nodo testigo $s$ y ejecuta los dos recorridos BFS en tiempo $O(m+n)$.
Lema del Nodo Testigo:
Un digrafo $G$ es fuertemente conexo si y solo si desde un nodo cualquiera $s$ se alcanzan todos los demás en $G$, y todos los nodos alcanzan a $s$ (verificado mediante BFS en $G^{rev}$).
Testigo (s)
Alcanzado en BFS
No alcanzable (Contraejemplo)