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 = \emptyset$

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 es que un grafo es bipartito si y solo si no tiene ciclos de longitud impar. Se ve trivialmente que un ciclo de longitud impar no se puede pintar con dos colores, y uno de longitud par sí. Bueno, se puede demostrar que si hay o no un ciclo de longitud impar en el grafo determino si es o no bipartito. Pueden leer la demostración en (link)