OIA-Wiki

Un grafo bipartito es un grafo cuyos vértices se pueden partir en 2 conjuntos disjuntos, $V_1$ y $V_1$, 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:

$$V_1 \cup V_2 = V$$

$$V_1 \cap V_2 = \varnothing$$

Algunos autores piden que $V_1$ y $V_2$ 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 $V_1$ y $V_2$) 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 \times 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, $v_0$, y lo ubicamos pore ejemplo en $V_1$, el siguiente del ciclo debe ser $v_1 \in V_2$. Pero luego debe ser $v_2 \in V_1$, y entonces debe ser $v_3 \in V_2$, y así siguiendo, los $v_i$ con $i$ impar van en $V_2$, y los $v_i$ con $i$ par van en $V_1$. 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 $V_1$) o impar (los ponemos en $V_2$) 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:

• Si la diferencia de distancias entre $d(s,u)$ y $d(s,v)$ fuera $1$, entonces uno tiene que estar en $V_1$ y el otro en $V_2$ (pues una distancia es par y la otra impar), y no hay problema en que sean vecinos.
• Es imposible que la diferencia de distancias entre $d(s,u)$ y $d(s,v)$ sea de 2 o más, pues de lo contrario se violaría automáticamente la desigualdad triangular entre los vértices $s,u,v$.

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.