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/26 19:12] sebach ↷ Links adapted because of a move operation |
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. |