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 1: | Línea 1: | ||
==Propiedades== | ==Propiedades== | ||
(Para todo G: grafo) | (Para todo G: grafo) | ||
Línea 16: | Línea 14: | ||
* (DEF) M es un '''matching maximo''' <=> no existe un camino alternado entre pares de nodos no saturados | * (DEF) M es un '''matching maximo''' <=> no existe un camino alternado entre pares de nodos no saturados | ||
* (TEO) Si M es un matching máximo y Rn un recubrimiento mínimo de los vertices de G -> |M|+|Rn|=n | * (TEO) Si M es un matching máximo y Rn un recubrimiento mínimo de los vertices de G -> |M|+|Rn|=n | ||
* (TEO) Si | * (TEO) Si S es un conjunto independiente maximo y Re un recubrimiento mínimo de los ejes de G -> |I|+|Re|=n | ||
* (DEF) Una '''red''' N es un grafo orientado conexo que tiene dos nodos distinguidos una fuente s con grado de salida positivo y un sumidero t con grado de entrada positivo. | * (DEF) Una '''red''' N es un grafo orientado conexo que tiene dos nodos distinguidos una fuente s con grado de salida positivo y un sumidero t con grado de entrada positivo. | ||
* (DEF) Una '''función de capacidades''' en la red es una función c(e)>=0 definida para todo e en EN | * (DEF) Una '''función de capacidades''' en la red es una función c(e)>=0 definida para todo e en EN | ||
Línea 45: | Línea 44: | ||
==Ejercicio 10.01:== | ==Ejercicio 10.01:== | ||
a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
Línea 51: | Línea 50: | ||
==Ejercicio 10.02:== | ==Ejercicio 10.02:== | ||
<br>a) | <br>a) F (Un grafo sin ejes no tiene) | ||
<br>b) F (Idem a) | |||
<br>b) F | |||
<br>c) V (En todo grafo, un solo vertice es conj. indep) | <br>c) V (En todo grafo, un solo vertice es conj. indep) | ||
<br>d) V (En todo grafo, todos los vertices forman un recub. de ejes) | <br>d) V (En todo grafo, todos los vertices forman un recub. de ejes) | ||
<br>e) V El matching maximo en peor caso tiene n/2 ejes (seria uno con todos los pares de vertices, salvo n impar, entonces queda uno aislado), que a su vez es el minimo de ejes de un recub. de vertices, por la misma razon -> |M| <= |Rv| | <br>e) V El matching maximo en peor caso tiene n/2 ejes (seria uno con todos los pares de vertices, salvo n impar, entonces queda uno aislado), que a su vez es el minimo de ejes de un recub. de vertices, por la misma razon -> |M| <= |Rv| | ||
<br>f) | <br>f) V El conjunto indep. maximo en peor tiene tiene n vertices, entonces cada uno estaria en un clique distinto, y entonces el recub. de ejes tiene como minimo n vertices en total -> |I| <= |Re| (mmm.. revisar) | ||
<br>g) F (Por ejemplo el primero grafo del 10.1) | <br>g) F (Por ejemplo el primero grafo del 10.1) | ||
==Ejercicio 10.03:== | ==Ejercicio 10.03:== | ||
<br>a) | <br>a) | ||
<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) | <br>c) | ||
<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) | <br>f) | ||
==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> | |||
Fin :P | |||
Posted by Alejandro | |||
==Ejercicio 10.06:== | ==Ejercicio 10.06:== | ||
==Ejercicio 10.07:== | ==Ejercicio 10.07:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
<br>d) | <br>d) | ||
==Ejercicio 10.08:== | ==Ejercicio 10.08:== | ||
<br>a) | <br>a) | ||
<br>b) | |||
<br>b) | <br>c) | ||
<br>c) | <br>d) | ||
<br>d) | |||
==Ejercicio 10.09:== | ==Ejercicio 10.09:== | ||
<br>a | <br>a) | ||
<br>b) | <br>b) | ||
<table bgcolor="blue"><tr><td><font color="white"> Flujo Maximo </font></td></tr></table> | <table bgcolor="blue"><tr><td><font color="white"> Flujo Maximo </font></td></tr></table> | ||
==Ejercicio 10.10:== | ==Ejercicio 10.10:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 10.11:== | ==Ejercicio 10.11:== | ||
==Ejercicio 10.12:== | ==Ejercicio 10.12:== | ||
<br>a) | <br>a) | ||
Línea 129: | Línea 117: | ||
==Ejercicio 10.14:== | ==Ejercicio 10.14:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 10.15:== | ==Ejercicio 10.15:== | ||
Asignar f(e) <math>\forall</math> e en un ciclo dirigido | Asignar f(e) <math>\forall</math> e en un ciclo dirigido | ||
Línea 144: | Línea 131: | ||
<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)) | ||
Posted By Alejandro | |||
==Ejercicio 10.16:== | ==Ejercicio 10.16:== | ||
==Ejercicio 10.17:== | ==Ejercicio 10.17:== | ||
==Ejercicio 10.18:== | ==Ejercicio 10.18:== | ||
==Ejercicio 10.19:== | ==Ejercicio 10.19:== | ||
==Ejercicio 10.20:== | ==Ejercicio 10.20:== | ||
==Ejercicio 10.21:== | ==Ejercicio 10.21:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 10.22:== | ==Ejercicio 10.22:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 10.23:== | ==Ejercicio 10.23:== | ||
==Ejercicio 10.24:== | ==Ejercicio 10.24:== | ||
Línea 190: | Línea 149: | ||
<br>b) | <br>b) | ||
==Ejercicio 10.25:== | ==Ejercicio 10.25:== | ||
<b>HECHO EN CLASE, ALGUIEN QUE LO TENGA SUBALO | <b>HECHO EN CLASE, ALGUIEN QUE LO TENGA SUBALO</b> | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
Línea 197: | Línea 156: | ||
<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) | ||
Línea 213: | Línea 165: | ||
<br>c) | <br>c) | ||
==Ejercicio 10.28:== | ==Ejercicio 10.28:== | ||