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 65: | Línea 65: | ||
<br>a) | <br>a) | ||
<br>=>) Sup. que hay un vertice aislado v. Entonces hay un eje que recubre a v -> v esta conectado a otro vertice -> ABS | <br>=>) Sup. que hay un vertice aislado v. Entonces hay un eje que recubre a v -> v esta conectado a otro vertice -> ABS | ||
<br><=) Si no hay vertices aislados -> siempre se puede recubrir los vertices eligiendo todos | <br><=) Si no hay vertices aislados -> siempre se puede recubrir los vertices eligiendo todos -> OK | ||
<br>b)Supongamos que NO. Sea k la cantidad de ejes con k < [n/2]. Si cada eje cubre 2 vertices, entonces cubrimos 2*k vertices, pero como k <[n/2] entonces 2*k < n. Por lo tanto cada eje debe cubrir mas de 2 vertices. Pero por definicion un eje incide sobre exactamente 2 vertices. ABS que provino de suponer que la cantidad de ejes es k < [n/2]. | <br>b)Supongamos que NO. Sea k la cantidad de ejes con k < [n/2]. Si cada eje cubre 2 vertices, entonces cubrimos 2*k vertices, pero como k <[n/2] entonces 2*k < n. Por lo tanto cada eje debe cubrir mas de 2 vertices. Pero por definicion un eje incide sobre exactamente 2 vertices. ABS que provino de suponer que la cantidad de ejes es k < [n/2]. | ||
<br>c)Si no fuera minimal. entonces siempre se podrian sacar ejes del recub. y nunca seria minimal -> ABS | <br>c)Si no fuera minimal. entonces siempre se podrian sacar ejes del recub. y nunca seria minimal -> ABS |