Herramientas de usuario
algoritmos-oia:grafos:grafos-bipartitos:maximo-matching-bipartito
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:grafos:grafos-bipartitos:maximo-matching-bipartito [2017/12/09 20:53] brianbok |
algoritmos-oia:grafos:grafos-bipartitos:maximo-matching-bipartito [2019/02/17 02:59] (actual) santo |
||
|---|---|---|---|
| Línea 50: | Línea 50: | ||
| Pensemos primero en la complejidad. Por qué no es muy alta, si hacemos una recursión que en principio podría tardar mucho. | 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: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. | + | 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í. | 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. | 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. | ||
| Línea 56: | Línea 56: | ||
| 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. | 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(V.E)$. 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)$. | + | 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. | 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. | ||
| Línea 62: | Línea 62: | ||
| <code cpp> | <code cpp> | ||
| - | |||
| #define forn(i,n) for(int i=0;i<(int)(n); i++) | #define forn(i,n) for(int i=0;i<(int)(n); i++) | ||
| + | |||
| int N, M; | int N, M; | ||
| + | |||
| vector< vector<int> > grafo; | vector< vector<int> > grafo; | ||
| vector<bool> visitada; | vector<bool> visitada; | ||
| vector<int> unidaA; | vector<int> unidaA; | ||
| + | |||
| bool hayMatchingParaLaPersona(int persona){ | bool hayMatchingParaLaPersona(int persona){ | ||
| forn(i, grafo[persona].size()){ | forn(i, grafo[persona].size()){ | ||
| Línea 85: | Línea 84: | ||
| } | } | ||
| + | |||
| int maximoMatching(){ | int maximoMatching(){ | ||
| - | unidaA.clear(); | + | unidaA.assign(M, -1); // Inicializamos en -1 y vamos guardando con quien esta matcheada la tarea i |
| - | forn(i, M){ | + | |
| - | unidaA.push_back(-1); // Inicializamos en -1 y vamos guardando con quien esta matcheada la tarea i | + | |
| - | } | + | |
| int result = 0; | int result = 0; | ||
| for (int persona = 0; persona < N; persona++){ | for (int persona = 0; persona < N; persona++){ | ||
| - | visitada.assign(n, -1); | + | visitada.assign(M, false); |
| // Corremos un "DFS" por cada persona, entonces tenemos que volver a inicializar el vector de tareas visitadas | // Corremos un "DFS" por cada persona, entonces tenemos que volver a inicializar el vector de tareas visitadas | ||
| - | } | ||
| if (hayMatchingParaLaPersona(persona)){ | if (hayMatchingParaLaPersona(persona)){ | ||
| result++; | result++; | ||
algoritmos-oia/grafos/grafos-bipartitos/maximo-matching-bipartito.1512852833.txt.gz · Última modificación: 2017/12/09 20:53 por brianbok
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
