8. Grafos bipartitos

8.1 Introducción

Muchos problemas relacionan objetos de dos tipos distintos: estudiantes con cursos, trabajadores con tareas, usuarios con productos o actores con películas.

Los grafos bipartitos representan estas situaciones dividiendo los vértices en dos conjuntos. Las aristas siempre cruzan de un conjunto al otro y nunca conectan dos vértices del mismo grupo.

8.2 Definición de grafo bipartito

Un grafo G = (V, E) es bipartito si su conjunto de vértices puede dividirse en dos subconjuntos disjuntos, generalmente llamados U y V.

Los conjuntos U y V forman una bipartición del grafo.

8.3 Conexiones permitidas

Si A y B pertenecen a U, no puede existir una arista entre ellos. Lo mismo ocurre con dos vértices de V. Solo se permiten aristas que crucen la bipartición.

8.4 Ejemplos de bipartición

8.5 Simulación interactiva: conecta dos conjuntos

Ajusta la cantidad de vértices de U y V. Selecciona dos nodos para crear una arista: la aplicación solo aceptará conexiones entre conjuntos diferentes.

Intenta seleccionar dos vértices rosados o dos celestes: la aplicación rechazará la arista. Pulsa Generar Kₘ,ₙ para conectar cada elemento de U con todos los de V.

8.6 Grafo bipartito completo

Un grafo bipartito es completo cuando cada vértice de U está conectado con todos los vértices de V. Se representa como K_m,n, donde m y n son los tamaños de ambos conjuntos.

K_3,4 tiene 3 + 4 = 7 vértices y 3 × 4 = 12 aristas.

8.7 Grados en Kₘ,ₙ

En un grafo bipartito completo, cada vértice de U se conecta con los n vértices de V. Cada vértice de V se conecta con los m vértices de U.

Por lo tanto, K_m,n es regular únicamente cuando m = n.

8.8 Bipartición y coloración

Un grafo es bipartito si sus vértices pueden colorearse utilizando solo dos colores de forma que los extremos de cada arista tengan colores diferentes.

Esta propiedad ofrece una forma algorítmica de comprobar la bipartición: recorremos el grafo y asignamos a cada vecino el color opuesto.

8.9 Representar un grafo bipartito en JavaScript

Podemos guardar los dos conjuntos por separado y representar cada arista como un par formado por un elemento de U y otro de V.

const estudiantes = ["Ana", "Bruno", "Carla"];
const cursos = ["JavaScript", "Python"];

const inscripciones = [
  ["Ana", "JavaScript"],
  ["Bruno", "Python"],
  ["Carla", "JavaScript"]
];

console.log("Vértices:", estudiantes.length + cursos.length);
console.log("Aristas:", inscripciones.length);

8.10 Validar una arista

Antes de agregar una conexión podemos verificar que sus extremos pertenezcan a grupos diferentes.

const U = new Set(["u1", "u2", "u3"]);
const V = new Set(["v1", "v2"]);

function aristaValida(a, b) {
  return (U.has(a) && V.has(b)) ||
         (V.has(a) && U.has(b));
}

console.log(aristaValida("u1", "v2"));
console.log(aristaValida("u1", "u3"));

8.11 Aplicaciones y emparejamientos

Los grafos bipartitos son la base natural de los problemas de emparejamiento, donde buscamos seleccionar aristas sin compartir extremos.

8.12 Errores comunes

• Conectar dos vértices que pertenecen al mismo conjunto.
• Suponer que toda división de vértices constituye una bipartición válida.
• Confundir un grafo bipartito con un grafo bipartito completo.
• Calcular m + n en lugar de m × n para las aristas de K_m,n.
• Creer que los dos conjuntos deben tener el mismo tamaño.
• Confundir los dos colores de la bipartición con atributos reales de los datos.

8.13 Qué debes recordar de este tema

• Un grafo bipartito divide sus vértices en dos conjuntos disjuntos.
• Las aristas solo conectan vértices de conjuntos diferentes.
• Un grafo bipartito puede colorearse correctamente con dos colores.
• K_m,n es el grafo bipartito completo con grupos de tamaños m y n.
• K_m,n posee m × n aristas.
• Los grafos bipartitos modelan asignaciones, compatibilidades y recomendaciones.

8.14 Conclusión

Los grafos bipartitos permiten representar con claridad relaciones entre dos tipos de objetos. Su estructura evita conexiones internas y facilita resolver problemas de asignación y emparejamiento.

En el próximo tema estudiaremos los grafos planares y analizaremos cuándo un grafo puede dibujarse sin que sus aristas se crucen.