¡Esta es una revisión vieja del documento!
Un grafo bipartito es un grafo cuyos vértices se pueden partir en 2 conjuntos disjuntos, V1 y V1, tales que cada vértice del grafo esté en exactamente uno, y no haya dos vértices del mismo conjunto tales que comparten una arista.
Es decir:
V1∪V2=V
V1∩V2=∅
Algunos autores piden que V1 y V2 sean no vacíos. La única diferencia es que eso hace que el grafo trivial (el de un único nodo) sea o no bipartito. Aquí consideraremos al grafo trivial como bipartito.
Estos grafos son interesantes ya que muchas situaciones pueden modelarse como un grafo bipartito: Personas que pueden ejercer varios trabajos (un conjunto de nodos son las personas, el otro los trabajos, y hay una arista si y solo si la persona puede ejercer ese trabajo); personas que pueden usar cada una un grupo distinto de bicicletas, por sus estaturas y comodidades... Al fin y al cabo, muchas situaciones verosimiles a la realidad se pueden modelar como un grafo bipartito.
Además, resulta que muchos problemas pueden resolverse más fácilmente en un grafo bipartito, que en el caso de un grafo general, del que nada conocemos. Esto hace que a veces sea útil poder darse cuenta de que estamos ante un grafo bipartito.
La bipartición (división en los dos conjuntos V1 y V2) no siempre es evidente del enunciado. Por ejemplo, si tenemos un grafo grilla, en el cual tenemos un nodo por cada casilla de una cuadrícula de n×m, y una arista entre dos nodos exactamente cuando las correspondientes casillas comparten un lado, el grafo grilla siempre es bipartito (Ejercicio: ¿Por qué? ¿Cómo es la bipartición?).
Como se ve en los artículos escritos sobre BFS y DFS, estos algoritmos son ideales para detectar si un grafo es bipartito o no. Simplemente arrancamos desde cualquier nodo, vamos pintando de colores distintos al vecino del cual vengo, y si puedo pintar todos sin tener adyacentes del mismo color, es bipartito; si no, no.
Una propiedad fundamental de los grafos bipartitos es el siguiente teorema:
TEOREMA:Un grafo es bipartito si y solo si no tiene ciclos simples de longitud impar.
Si un ciclo simple tiene longitud impar, es imposible formar la separación en dos conjuntos: si empezamos por un nodo cualquiera del ciclo, v0, y lo ubicamos pore ejemplo en V1, el siguiente del ciclo debe ser v1∈V2. Pero luego debe ser v2∈V1, y entonces debe ser v3∈V2, y así siguiendo, los vi con i impar van en V2, y los vi con i par van en V1. Pero como el ciclo tiene longitud total impar, al haber pintado todos los nodos y “completar la vuelta al ciclo”, el primero y el último quedan como vecinos y del mismo color, con lo cual no es posible que sea bipartito.
Si no hay ciclos de longitud impar, el grafo es bipartito. Para verlo, basta tomar un nodo origen s arbitrario y separar a todos los nodos según si están a distancia par (los ponemos en V1) o impar (los ponemos en V2) de este origen (si no es conexo el grafo, se hace lo mismo en cada componente conexa). La única manera de que esto falle, y no la propuesta dada no sea una bipartición válida, es que haya dos vértices u y v adyacentes, a una misma distancia d del origen:
Pero entonces, tomando esa arista (u,v), junto con caminos mínimos P_1 de s a u, y P_2 de s a v, entre los 3 se forma un ciclo, de longitud total 2d+1$, que es impar. De cualquier ciclo impar se puede extraer un ciclo simple impar, así que en este caso se concluye que si esto pasa es porque el grafo directamente no era bipartito.
: Hablar del algoritmo de bipartición basado en “duplicar los nodos”, guardando en cada uno la paridad con que se llegó. Esa idea general es importante en otros problemas.