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 | |||
|
algoritmos-oia:grafos:grafos-bipartitos:maximo-matching-bipartito [2017/12/26 19:13] sebach ↷ Page moved from algoritmos-oia:maximo-matching-bipartito to algoritmos-oia:grafos:grafos-bipartitos:maximo-matching-bipartito |
algoritmos-oia:grafos:grafos-bipartitos:maximo-matching-bipartito [2019/02/17 02:59] (actual) santo |
||
|---|---|---|---|
| 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. | ||
algoritmos-oia/grafos/grafos-bipartitos/maximo-matching-bipartito.1514315586.txt.gz · Última modificación: 2017/12/26 19:13 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
