OIA-Wiki

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

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.

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)