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 t1, ahora pruebo con t2. Supongamos que encuentro un camino que dice "está bien, te libero a la tarea t2, me encargo de no perder a ninguna persona del matching, y así ganamos 1". Y supongamos que la tarea t1 está en el camino. Bueno, pero entonces podemos cortar la primera parte del camino, y empezar con la arista (i,t1). A partir de t1 seguir el camino encontrado, y así obtener un camino de aumento con la arista (i,t1). Pero vimos que esto no se podía porque ya habíamos probado unir i con t1. Obtenemos un absurdo, que viene de suponer que hay un camino de aumento que usa la tarea t1. 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 t1, ahora pruebo con t2. Supongamos que encuentro un camino que dice "está bien, te libero a la tarea t2, me encargo de no perder a ninguna persona del matching, y así ganamos 1". Y supongamos que la tarea t1 está en el camino. Bueno, pero entonces podemos cortar la primera parte del camino, y empezar con la arista (i,t1). A partir de t1 seguir el camino encontrado, y así obtener un camino de aumento con la arista (i,t1). Pero vimos que esto no se podía porque ya habíamos probado unir i con t1. Obtenemos un absurdo, que viene de suponer que hay un camino de aumento que usa la tarea t1. 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).EnrealidadlacomplejidaddelDFSesO(V+E),peroE>=V/2(suponiendoquenohaynodossueltosquetienesentidoporquenoimportanparaelmatching),entoncesO(V+E)=O(E)$. | + | La complejidad entonces queda como un DFS por cada persona, $\large O(VE).EnrealidadlacomplejidaddelDFSesO(V+E),peroE>=V/2(suponiendoquenohaynodossueltosquetienesentidoporquenoimportanparaelmatching),entoncesO(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
