OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
===== Matching en un grafo bipartito =====

Como vimos, un grafo bipartito puede ser una situación cotidiana, donde algunas personas pueden estar asociadas a algunas ciertas tareas cada una, por ejemplo. Algo interesante es **asignar** a ciertas personas ciertas tareas, de manera que no haya dos personas con la misma tarea asociada, y que nadie tenga más de una tarea. Esta asociación, en nuestro grafo va a consistir en una selección de aristas, de manera que cada nodo forme parte de a lo sumo una arista.

Este tipo de selección de aristas se llama matching, emparejamiento.

===== Máximo matching =====

Un máximo matching de un grafo bipartito, es un matching que tiene máxima cantidad de aristas.
El algoritmo que vamos a llevar a cabo es algo medio fuerza-brutesco.

Llamémosle a un conjunto de nodos las personas, y al otro tareas.
Lo que vamos a hacer es probar para cada persona, si podés asignarle un trabajo de manera que este trabajo no esté asignado. Si está asignado a otra persona, probamos liberar esa unión, y para no perder a esta segunda persona, ahora la intentamos unir a alguna otra tarea.
Intuitivamente se puede ver que esta función va a ser recursiva, es decir la función "unir con alguna tarea libre" se va a llamar a sí misma cuando intente unir con una tarea asignada. Libera la unión de esta tarea y ahora quiere "unir con alguna tarea libre" a la persona que acaba de liberar.
Para leer un poco de recursión pueden consultar [[algoritmos-oia:recursion|este]] link.

===== Ejemplo =====

Supongamos que tenemos el siguiente grafo bipartito:

{{:algoritmos-oia:bipartite-0.png?400|}}


Entonces agarramos a la primera persona, y nos preguntamos, "puedo asignarle la tarea $5$?". Sí, entonces asignamos.

{{:algoritmos-oia:bipartite-1.png?400|}}

Ahora, agarramos a la segunda persona. Podemos asignarle la tarea $7$? Sí, asignamos

{{:algoritmos-oia:bipartite-2.png?400|}}

Miramos la tercera persona. Como el recorrido de las aristas va a en cualquier orden (según cómo tengamos la entrada del grafo por ejemplo), no podemos garantizar que vamos a preguntarnos por la asignación de la tarea número $8$. Supongamos entonces que buscamos asignarle la tarea $7$. Como no está libre, intentamos liberarla. Sabemos que si está unida, está unida a exactamente una persona. Entonces vemos si podemos liberar a la tarea $7$, pero sin perdiendo de nuestro matching a la persona $2$. Entonces corremos esta función de "unir con alguna tarea libre" para la persona $2$.

{{:algoritmos-oia:bipartite-3.png?400|}}

Encontramos que la tarea $6$ está libre y se la podemos asignar. La asignamos y nuestro matching creció con la persona $3$.

{{:algoritmos-oia:bipartite-5.png?400|}}

Miramos a la persona $4$, a ver si le podemos asignar la tarea $9$ (de vuelta, el orden depende de cómo tengamos el grafo). Podemos, entonces la asignamos y nuestro matching creció en $1$.

{{:algoritmos-oia:bipartite-4.png?400|}}

Terminamos con un matching de tamaño $4$.


===== Algoritmo =====

==== Complejidad ====

Pensemos primero en la complejidad. Por qué no es muy alta, si hacemos una recursión que en principio podría tardar mucho.
Lo copado de este algoritmo es que funciona como un [[algoritmos-oia:grafos:dfs|DFS]]. Es decir, cuando llamamos a la función "unir con alguna tarea libre", lo que hacemos no va a recorrer ninguna arista más de una vez.
Primero, llamemos "camino de aumento" a un camino como el de la cuarta figura, que empieza en el nodo $3$, va al $7$, luego al $2$ y por último al $6$. Lo que interesa de este tipo de caminos es que empiezan por un nodo libre (porque empieza preguntándome si puedo agregar a la persona $3$ al matching), termina en un nodo libre (porque si la tarea $6$ estuviera ocupada habría que desocuparla y seguir el camino), y alternan, una arista que no está en el matching, con una que sí.
Se puede probar que el matching es máximo si y solo si no existe un camino de aumento. Una de las dos demostraciones es fácil de ver. Si encontramos un camino de aumento, entonces basta con borrar las aristas que estaban en el matching, y luego poner en nuestro matching las otras aristas. Por la alternancia, lo que nos queda es un matching, y tiene una arista más que antes.

Supongamos que estoy intentando unir a la persona $i$. Ya probé unirla con la tarea $t_1$, ahora pruebo con $t_2$. Supongamos que encuentro un camino que dice "está bien, te libero a la tarea $t_2$, me encargo de no perder a ninguna persona del matching, y así ganamos $1$". Y supongamos que la tarea $t_1$ está en el camino. Bueno, pero entonces podemos cortar la primera parte del camino, y empezar con la arista $(i, t_1)$. A partir de $t_1$ seguir el camino encontrado, y así obtener un camino de aumento con la arista $(i, t_1)$. Pero vimos que esto no se podía porque ya habíamos probado unir $i$ con $t_1$. Obtenemos un absurdo, que viene de suponer que hay un camino de aumento que usa la tarea $t_1$. Entonces, no vamos a mirar una tarea más de una vez.

La complejidad entonces queda como un DFS por cada persona, $\large O(VE)$. En realidad la complejidad del DFS es $O(V+E)$, pero $E>=V/2$ (suponiendo que no hay nodos sueltos que tiene sentido porque no importan para el matching), entonces $O(V+E)=O(E)$.

Llamaremos $N$ a nuestra cantidad de personas, y $M$ a la cantidad de tareas. Vamos a tener un $vector< vector<int> > grafo$ donde en el vector $i$ tiene los números de tareas. Podemos enumerar a las personas y las tareas del $1$ al $N$ y al $M$ respectivamente. Es decir, no hace falta que tengan números distintos por más que sean nodos del mismo grafo.
También vamos a querer saber si una tarea fue visitada en un "dfs", con un $vector<bool> visitada$, y a quién está unida, con un $vector<int> unidaA$.

<code cpp>
#define forn(i,n) for(int i=0;i<(int)(n); i++)
 
int N, M;
 
vector< vector<int> > grafo;
vector<bool> visitada;
vector<int> unidaA;
 
bool hayMatchingParaLaPersona(int persona){
    forn(i, grafo[persona].size()){
        int tarea = grafo[persona][i];
        if (!visitada[tarea]){
            visitada[tarea] = true;
            if (unidaA[tarea] == -1 || hayMatchingParaLaPersona(unidaA[tarea]) ){
                unidaA[tarea] = persona;
                return true;
            }
        }
    }
    return false;
}
 
 
int maximoMatching(){
    unidaA.assign(M, -1); // Inicializamos en -1 y vamos guardando con quien esta matcheada la tarea i
    int result = 0;
    for (int persona = 0; persona < N; persona++){
        visitada.assign(M, false);
        // Corremos un "DFS" por cada persona, entonces tenemos que volver a inicializar el vector de tareas visitadas
        if (hayMatchingParaLaPersona(persona)){
            result++;
        }
    }
    return result;
}

</code>

Y el main del grafo de las imágenes queda:

<code cpp>
int main(){
    N=4+1; // sumo 1 para indexar en 1. Si meto nodos sueltos (en este caso la persona 0), no afectan al algoritmo.
    M=5+N; // sumo N+1 para poder tener las tareas 5, 6, 7, 8, 9 (el 1 es para indexar en 1). Los nodos de tareas 0, 1, 2, 3, 4 están sueltos
    grafo.resize(N);
    grafo[1] = {5, 6};
    grafo[2] = {7, 6};
    grafo[3] = {7, 8};
    grafo[4] = {9, 8};
    cout<<"El maximo matching del grafo tiene "<<maximoMatching()<<" aristas"<<endl;
    cout<<"Las uniones son:"<<endl; //Como tenemos la variable global unidaA, la aprovechamos para ver las uniones
    forn(i, M){
        if(unidaA[i]!=-1){
            cout<<"La persona "<<unidaA[i]<<" realiza la tarea "<<i<<endl;
        }
    }
}

</code>


===== Problemas para practicar =====

[[https://open.kattis.com/problems/gopher2|Gopher 2]] (este tiene un poquito de geometría también. No dice complejidades pero $n*m$ entra)

[[https://open.kattis.com/problems/paintball|Paintball]]
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
