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 69: | Línea 69: | ||
<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 | ||
<br>d)Si un recub. de vertices contiene ciclos -> hay vertices cubiertos por mas de 1 eje -> no es minimal -> ABS. Si un recub. de ejes contiene ciclos -> hay ejes cubiertos por mas de 1 vertices -> no es minimal -> ABS | <br>d)Si un recub. de vertices contiene ciclos -> hay vertices cubiertos por mas de 1 eje -> no es minimal -> ABS. Si un recub. de ejes contiene ciclos -> hay ejes cubiertos por mas de 1 vertices -> no es minimal -> ABS | ||
<br>e)n-1. Si | <br>e)n-1. Si habría más, habría un ciclo, y luego se podría sacar un eje. Será minimal ya que si sacamos algun eje, luego es posible que haya un vertice que quede sin cubrir. | ||
<br>f)Si existe un camino con long >= 3, por ej. a-b-c-d, entonces hay vertices cubiertos por 2 ejes (cuando se podria haber evitado elegir el eje b-c) -> no es minimal. La vuelta se hace suponiendo que no es minimal. | <br>f)Si existe un camino con long >= 3, por ej. a-b-c-d, entonces hay vertices cubiertos por 2 ejes (cuando se podria haber evitado elegir el eje b-c) -> no es minimal. La vuelta se hace suponiendo que no es minimal. | ||
Línea 87: | Línea 87: | ||
==Ejercicio 10.06:== | ==Ejercicio 10.06:== | ||
Ehh.. otro dia con mas tiempo lo analizo | |||
==Ejercicio 10.07:== | ==Ejercicio 10.07:== | ||
Línea 143: | Línea 143: | ||
<br>Si e1,e2,ei... es un camino de S a T tq f(ei) > c(ei) <math>\forall</math>i -> es camino de disminucion | <br>Si e1,e2,ei... es un camino de S a T tq f(ei) > c(ei) <math>\forall</math>i -> es camino de disminucion | ||
<br>... Y podemos disminuir el flujo del camino en min(f(ei)-c(ei)) | <br>... Y podemos disminuir el flujo del camino en min(f(ei)-c(ei)) | ||
==Ejercicio 10.16:== | ==Ejercicio 10.16:== | ||
==Ejercicio 10.17:== | ==Ejercicio 10.17:== | ||
Despues lo dibujo | |||
==Ejercicio 10.18:== | ==Ejercicio 10.18:== | ||
Línea 172: | Línea 165: | ||
==Ejercicio 10.21:== | ==Ejercicio 10.21:== | ||
<br>a) =>) | <br>a) (Revisar) =>) Facil <=) Sup. no fueran disjuntos. Existe un corte de menos de k arcos ABS | ||
<br>b) | <br>b) | ||
Línea 197: | Línea 184: | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
<br>d) | <br>d) | ||
<br>e) | <br>e) | ||
<br>f) | <br>f) | ||
==Ejercicio 10.27:== | ==Ejercicio 10.27:== | ||
<br>a) | <br>a) |