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. | ||
Posted by Alejandro | |||
==Ejercicio 10.06:== | ==Ejercicio 10.06:== |