En este manual, definiremos el emparejamiento máximo de un grafo bipartito, aprenderemos a encontrarlo y comentaremos la relación de este problema con otros problemas y algoritmos de grafos.
Definiciones
Un grafo bipartito, como probablemente hayáis visto ya, es un grafo no dirigido cuyos nodos se pueden partir en dos conjuntos $A$ y $B$ (posiblemente vacíos) tal que no haya ninguna arista conectando dos nodos del mismo conjunto. Y un emparejamiento de un grafo consiste en una selección de aristas de forma que no podamos coger ningún nodo del grafo que conecte a dos aristas del conjunto. Puesto de otra forma, no existe un nodo $u$ tal que haya dos nodos $v$ y $w$ tales que $(u, v)$ y $(u, w)$ sean aristas del conjunto. Por lo tanto, el problema del emparejamiento máximo consiste en encontrar un emparejamiento del grafo de entrada que contenga el máximo número posible de aristas que puede contener un emparejamiento del grafo dado.
Para explicar el algoritmo de Kuhn, contaremos con que hemos dividido ya los nodos de nuestro grafo $G = (V, E)$ en los conjuntos $A$ y $B$ (aunque esto no hará falta luego en nuestra implementación), pudiendo así dibujar el grafo sobre papel como dos conjuntos de nodos en hilera con aristas conectando nodos de una hilera a otra:
Definiremos ahora un par de conceptos para poder explicar bien el algoritmo:
- Nodo saturado: dado un emparejamiento del grafo, llamaremos saturado a un nodo si en el emparejamiento hay una arista conectada al nodo.
- Camino alterno: dado un emparejamiento del grafo, este será un camino con aristas que se van alternando una sí y una no entre estar incluidas en el emparejamiento y no estarlo.
- Camino incremento: dado un emparejamiento del grafo, este será un camino alterno cuyo primer y último nodo no estarán saturados.
Algoritmo de Kuhn
El algoritmo de Kuhn se basa en el lema de Berge, que demostró que un emparejamiento $M$ del grafo será máximo si y solamente si no hay un camino incremento en relación a $M$. En resumen, el algoritmo de Kuhn parte de un emparejamiento vacío y, mientras sea posible encontrar un camino incremento en relación al emparejamiento, lo haremos, cambiando el emparejamiento con esta nueva información. Esto deja dos preguntas por responder: qué hacer con el emparejamiento al encontrar un camino incremento y cómo encontrar tal camino incremento.
Pongamos que tenemos un emparejamiento $M = \{(u_1, v_1), \dots, (u_k, v_k)\}$ y que encontramos un camino incremento, de forma que la primera arista del camino no está en $M$, la segunda sí, la tercera no, etc., alternando hasta llegar a la última, que tampoco está en $M$. Por cómo hemos definido los caminos incrementos, podemos observar que las aristas del camino que no están en $M$ forman un emparejamiento $M'$ y que hay una arista más en el camino que está fuera de $M$ de las que hay en $M$. Por lo tanto, si cambiamos las aristas del camino en $M$ por las que están fuera, la cardinalidad de $M$ (es decir, su número de aristas) aumentará por 1. Además, como en los caminos incremento el primer y último nodo no está en el emparejamiento, sabemos que este cambio no hará que $M$ deje de ser un emparejamiento.
Ahora solo nos falta responder cómo podemos encontrar en el grafo un camino incremento, dado un emparejamiento $M$. Iteraremos sobre todos los nodos de $A$, viendo si ya están saturados o no. Si no es el caso, iniciaremos una DFS desde el nodo actual, tratando de encontrar un camino alterno hasta otro nodo no saturado. Esta DFS funcionará de la siguiente forma:
- Iniciamos la DFS desde un nodo no saturado $u$. Definimos un camino actual vacío.
- Miramos si hay una arista $(u, v)$ siendo $v$ un nodo no saturado. Si esta arista existe, este es un camino incremento y ya hemos terminado.
- Si esta arista no existe, cogeremos una arista arbitraria $(u, w)$ y haremos que $u-w-v$ sea el camino actual, llamando $v$ al nodo del conjunto $A$ conectado a $w$ en el emparejamiento.
- Trataremos de nuevo de encontrar un nodo no saturado $x$ conectado a $w$. Si lo encontramos, $u-w-v-x$ será un camino incremento y podremos parar de buscar. Si no, procederemos por cualquier arista conectada a $w$ mientras esta no cree un ciclo en el camino actual, y así sucesivamente hasta encontrar un camino incremento o concluir que uno no existe. Iremos haciendo backtracking, quitando aristas al camino actual, como haríamos en una DFS normal para llegar a esta conclusión.
Si alguna DFS encuentra un camino incremento cambiaremos el emparejamiento actual como expliqué antes y volveremos a empezar a iterar sobre los nodos. Si ninguna DFS encuentra un camino incremento, podremos concluir por el lema de Berge que el emparejamiento actual es máximo.
Implementación
Veremos ahora cómo implementar esta explicación de forma concisa. Siempre podéis tratar de implementar el algoritmo vosotros para aseguraros de que lo habéis entendido bien, comprobando vuestra explicación con el problema CSES- School Dance.
Aquí nos dan ya el grafo partido en los conjuntos $A$ y $B$, pero en caso de que no nos los den, siempre podemos iniciar la DFS desde todo nodo no saturado y funcionaría el algoritmo bien igual.
Además, podemos demostrar que no es necesario volver a empezar por el nodo 0 cada vez que actualicemos el emparejamiento, sino que nos sirve un único pase por todos los nodos del grupo de la izquierda, actualizando el emparejamiento sobre la marcha. Aquí tenéis la implementación comentada:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> adjList;
vector<bool> visitado; // guarda qué nodos del grupo de la izquierda hemos visitado con la DFS actual
vector<int> conexion; // guarda la conexión seleccionada en la izquierda de los nodos de la derecha (-1 si no la hay)
int n, m;
// Esta función realiza una DFS para encontrar un camino incremento.
// Va reescribiendo el emparejamiento a medida que encuentra el camino, de forma similar
// a otras funciones de backtracking. Retorna true si lo ha encontrado y false en caso contrario.
bool caminoIncremento(int u) {
if (visitado[u]) {
// no podemos usar un nodo en dos aristas
return false;
}
visitado[u] = true;
// probamos a incrementar el camino por todos los nodos vecinos a ver si alguno lo hace
for (int & vecino: adjList[u]) {
if (conexion[vecino] == -1 || caminoIncremento(conexion[vecino])) {
// encontramos un camino incremento con la arista (u, vecino) -> actualizamos el emparejamiento
conexion[vecino] = u;
return true;
}
}
// no hemos encontrado ningún camino incremento por esta vía
return false;
}
void encontrarEmparejamiento() {
conexion.assign(n+m, -1); // aunque solo usemos las m posiciones finales, esto nos simplifica
// la implementación. En casos justos de memoria, podemos quitar esas n posiciones.
for (int i = 0; i < n; i++) {
visitado.assign(n, false);
caminoIncremento(i);
}
int numParejas = m - count(conexion.begin()+n, conexion.end(), -1);
// el número de parejas también se puede obtener contando cuántas llamadas a caminoIncremento retornan true.
cout << numParejas << '\n';
for (int i = n; i < n+m; i++) {
if (conexion[i] != -1) {
cout << conexion[i]+1 << ' ' << i-n+1 << '\n';
}
}
}
int main() {
int k, a, b;
cin >> n >> m >> k;
adjList = vector<vector<int>>(n+m);
while(k--) {
cin >> a >> b;
a--;
b = b - 1 + n;
adjList[a].push_back(b);
adjList[b].push_back(a);
}
encontrarEmparejamiento();
return 0;
}
Complejidad
Podremos incrementar el emparejamiento vacío $O(|V|)$ veces y esto implica la complejidad de una DFS en cada una de estas ocasiones. Por lo tanto, el algoritmo de Kuhn tarda $O(|V| |E|)$ en ejecutarse.
Comienzo rápido
Habrá problemas donde te sea fácil encontrar un emparejamiento en el grafo con $k$ aristas. Siempre será mejor empezar por ahí en lugar de por el emparejamiento vacío, para así ahorrarte esas primeras $k$ iteraciones. También es común (aunque la mayoría de problemas no lo requieren para obtener el AC) encontrar tal emparejamiento con una heurística, por ejemplo iterando sobre las aristas y, de forma voraz, añadiéndolas al emparejamiento actual si ninguno de sus nodos está ya saturado.
Algoritmos alternativos
El emparejamiento máximo se puede encontrar a través de algoritmos de max-flow, aunque estos no son más rápidos que el algoritmo de Kuhn, explicado aquí, que resuelve directamente el problema del emparejamiento máximo. Esto se debe a que el problema del máximo emparejamiento se puede reducir al problema de max-flow. Algunos ejemplos de estos algoritmos, que sirven en muchos más contextos, son Ford-Fulkerson y Edmonds-Karp. Además, sus implementaciones son menos concisas que esta, por lo que en los concursos, donde el tiempo apremia, es muy recomendable usar el algoritmo de Kuhn.
Un algoritmo que sin embargo sí es más rápido que el de Kuhn es el de Hopcroft-Karp, que aunque está fuera de lo esperado de vosotros de momento, puede resultaros de interés (por pura curiosidad) conocer. Este tiene complejidad de $O(|E| \sqrt{|V|})$.
Relaciones interesantes con otros problemas de grafos
El problema de la mínima cobertura de vértices (minimum vertex cover) consiste en, dado un grafo $G = (V, E)$, encontrar el conjunto de nodos de menor cardinalidad (es decir, menor número de nodos) tal que cualquier arista $(u, v) \in E$ cumpla que $u \in V$ o $v \in V$.
Para grafos generales, este problema es NP-hard, que significa que con las clases de algoritmos conocidas actualmente, para grafos muy pequeños ya resulta impracticable resolverlo. Sin embargo, para grafos bipartitos se da la circunstancia (teorema de König) de que la cardinalidad del emparejamiento máximo es la misma que la de la mínima cobertura de vértices. Por lo tanto, nos basta con resolver este problema, bastante más sencillo, para encontrar la cardinalidad de la cobertura.
Dónde leer si os interesa saber más
A mí me resultó muy útil cuando aprendí este algoritmo, y para explicarlo mejor en el manual, tanto la explicación de CP-Algorithms como la sección correspondiente en el libro Competitive Programming 3.
Añadir nuevo comentario