Edición de «Práctica 10: Matching - Flujo Máximo (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 85: | Línea 85: | ||
Como G es bipartito vale que <math>gr(v) \leq max(|V1|,|V2|)</math> para todo nodo. Sumando sobre los nodos del recubrimiento de aristas, Re, queda que <math>\sum gr(v) \leq max(|V1|,|V2|).\beta</math>. Como Re es un recubrimiento de aristas, sus nodos tocan todos los ejes, con lo cual <math>\sum gr(v) \geq m</math>, y listo. | Como G es bipartito vale que <math>gr(v) \leq max(|V1|,|V2|)</math> para todo nodo. Sumando sobre los nodos del recubrimiento de aristas, Re, queda que <math>\sum gr(v) \leq max(|V1|,|V2|).\beta</math>. Como Re es un recubrimiento de aristas, sus nodos tocan todos los ejes, con lo cual <math>\sum gr(v) \geq m</math>, y listo. | ||
'''Otra forma simple y en criollo:''' | |||
En un bipartito '''sin nodos aislados''' entonces alfa y beta son iguales al maximo entre |P1| y |P2| dado que el maximo conjunto independiente va a ser el tamaño de la partición más grande, y el minimo numero de aristas que se necesitan para cubrir a todos los nodos también, porque sino va a haber nodos en la particion grande que van a quedar sin cubrir. | |||
Ademas, m <= |P1|*|P2| porque a lo sumo se tiene tantas aristas como en el completo que "le corresponde". | |||
En contreto, sea M el maximo entre |P1| y |P2|, por lo anterior | |||
alfa = beta = M | |||
Entonces: | |||
m <= |P1|*|P2| <= M*M = alfa*beta | |||
Y si '''se tiene k nodos aislados''' entonces aglutinamos todos | |||
los nodos aislados en la particion mas grande. | |||
Ahora ellos no contribuyen aristas, con lo cual, si llamamos n' y m' al numero de nodos y aristas del grafo que resulta de eliminar los k nodos aislados, se tiene que: | |||
m' = m y n' = n - k <= n | |||
y ademas | |||
alfa' = alfa - k | |||
donde alfa' es el conjunto independiente maximo del grafo sin los nodos aislados. | |||
Ahora, por lo anterior tenemos que beta' = beta (porque no cambiamos las aristas) y que: | |||
m' <= alfa' * beta' = (alfa - k) beta <= alfa * beta | |||
==Ejercicio 10.06:== | ==Ejercicio 10.06:== |