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 | <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 | ||
==Ejercicio 10.04:== | ==Ejercicio 10.04:== | ||
Si G tiene un conjunto independiente de n nodos, entonces cada uno esta en un clique distinto, y el cubrimiento minimo tiene por lo menos n cliques -> |I|<=|Rn| | |||
==Ejercicio 10.05:== | ==Ejercicio 10.05:== | ||
Probar que si G es bipartito, m <= <math>\alpha * \beta </math>, donde <math>\alpha</math>=#(conj. indep. maximo) y <math>\beta</math>=#(Recubrimiento minimo de aristas) | Probar que si G es bipartito, m <= <math>\alpha * \beta </math>, donde <math>\alpha</math>=#(conj. indep. maximo) y <math>\beta</math>=#(Recubrimiento minimo de aristas) | ||
<br>Sea: <math>v \in \real</math>, y V1,V2 las particiones de G | |||
<br><math>m \leq 2*m = \sum d(v) \leq max(|V1|,|V2|)* \beta \leq \alpha * \beta </math> | |||
==Ejercicio 10.06:== | ==Ejercicio 10.06:== | ||
Ehh.. otro dia con mas tiempo lo analizo | |||
==Ejercicio 10.07:== | ==Ejercicio 10.07:== | ||
Línea 96: | Línea 90: | ||
==Ejercicio 10.08:== | ==Ejercicio 10.08:== | ||
<br>a)El algoritmo asigna a cada conj. indep. maximo un color, por lo tanto no habra vertices adyacentes con el mismo color | <br>a)El algoritmo asigna a cada conj. indep. maximo un color, por lo tanto no habra vertices adyacentes con el mismo color | ||
<br>b)Y..como es NP-Completo debe ser fea :P | <br>b)Y..como es NP-Completo debe ser fea :P | ||
<br>c) | <br>c)Creo que si | ||
<br>d)MM.. puede ser | <br>d)MM.. puede ser | ||
Línea 109: | Línea 102: | ||
==Ejercicio 10.10:== | ==Ejercicio 10.10:== | ||
<br>a)s | <br>a)s-b-t y s-c-b-t | ||
<br>b)F=4 | <br>b)F=4 | ||
<br>c)No es lo mismo que b)? | <br>c)No es lo mismo que b)? | ||
Línea 143: | Línea 136: | ||
<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:== | ||
==Ejercicio 10.19:== | ==Ejercicio 10.19:== | ||
Agregar s conectado a x1, x2, x3, con capacidad 5, 10, 5 respectivamente, y agregar t conectado a y1, y2, y3 con flujo entre [5..inf],[10..inf],[5..inf] respectivamente | Agregar s conectado a x1, x2, x3, con capacidad 5, 10, 5 respectivamente, y agregar t conectado a y1, y2, y3 con flujo entre [5..inf],[10..inf],[5..inf] respectivamente | ||
Línea 172: | Línea 149: | ||
==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) | ||
==Ejercicio 10.22:== | ==Ejercicio 10.22:== | ||
<br>a) | <br>a)Con DFS sacando ejes usados | ||
<br>b) | <br>b)Con DFS sacando vertices usados | ||
==Ejercicio 10.23:== | ==Ejercicio 10.23:== | ||
Línea 197: | Línea 168: | ||
<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) |