Matching bipartito (Kuhn)
Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI
📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.
Qué hace
Emparejamiento máximo en un grafo bipartito buscando caminos aumentantes con DFS.
Complejidad: O(V·E) en el peor caso.
Cuándo usarlo
Asignaciones uno-a-uno, teorema de König (cobertura mínima = matching máximo), Hall. En IOI los tamaños se diseñan para que Kuhn baste.
Implementación recomendada (C++)
struct Kuhn {
int nL, nR; vector<vector<int>> g;
vector<int> matchR; vector<char> used;
Kuhn(int nL, int nR) : nL(nL), nR(nR), g(nL), matchR(nR, -1) {}
void add(int u, int v) { g[u].push_back(v); } // u en [0,nL), v en [0,nR)
bool try_kuhn(int u) {
for (int v : g[u]) if (!used[v]) {
used[v] = 1;
// v está libre, o su pareja actual puede reubicarse ⇒ nos quedamos con v
if (matchR[v] == -1 || try_kuhn(matchR[v])) { matchR[v] = u; return true; }
}
return false;
}
int max_matching() {
int res = 0;
for (int u = 0; u < nL; u++) { used.assign(nR, 0); if (try_kuhn(u)) res++; }
return res;
}
};⚠️ Notas
Lo difícil casi nunca es el algoritmo, sino modelar el problema como bipartito: quién va a la izquierda, quién a la derecha y qué significa una arista. Teorema de König: en un grafo bipartito, el tamaño del matching máximo es igual al del mínimo conjunto de vértices que toca todas las aristas. Hopcroft-Karp y el matching general (Blossom) están fuera del syllabus — ver Syllabus IOI.