Edición de «Práctica 11: 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 129: | Línea 129: | ||
==Ejercicio 11.14:== | ==Ejercicio 11.14:== | ||
<br>a) Hay contraejemplo | <br>a)Hay contraejemplo | ||
<br>b) | <br>b) | ||
==Ejercicio 11.15:== | ==Ejercicio 11.15:== | ||
Línea 146: | Línea 146: | ||
<br> | <br> | ||
No pense lo que pusieron arriba, pero lo saque de un libro y decia que se hacia en dos pasos. el primero es ver si el flujo es factible. el segundo paso es convertir el problema haciendo que todos las cotas inferiores sean cero. esto se logra haciendo que en la red residual rij = (uij-xij)+(xij-lij) donde uij es la cota de capacidad del arco y lij la cota inferior del flujo. (por las dudas ver , Network Flows,Ravindra K. Ahuja,Thomas L. Magnanti,James B. Orlin pag 192) | No pense lo que pusieron arriba, pero lo saque de un libro y decia que se hacia en dos pasos. el primero es ver si el flujo es factible. el segundo paso es convertir el problema haciendo que todos las cotas inferiores sean cero. esto se logra haciendo que en la red residual rij = (uij-xij)+(xij-lij) donde uij es la cota de capacidad del arco y lij la cota inferior del flujo. (por las dudas ver , Network Flows,Ravindra K. Ahuja,Thomas L. Magnanti,James B. Orlin pag 192) | ||
==Ejercicio 11.16:== | ==Ejercicio 11.16:== | ||
Línea 189: | Línea 186: | ||
==Ejercicio 11.23:== | ==Ejercicio 11.23:== | ||
==Ejercicio 11.24:== | |||
<br>a) | |||
<br>b) | |||
==Ejercicio 11.25:== | |||
<b>HECHO EN CLASE, ALGUIEN QUE LO TENGA SUBALO (por favor)</b> | |||
<br>a) | |||
<br>b) | |||
==Ejercicio 11.26:== | |||
<br>a) | |||
<br>b) | |||
<br>c) En un corte la capacidad esta dada por : | |||
<br> <math> \sum_{e \in SS^c} c_{ij} - \sum_{e \in S^cS} b_{ij} </math> | |||
<br> Observacion : Comparar esto con el corte cuando no hay limite inferior, aca estamos obligados a mandar flujo encontra. | |||
<br> Supongamos <math> v </math> el valor de un flujo valido y el flujo que pasa por cada arista <math> x_{ij} </math>. Entonces | |||
<br> <math> v = \sum_{e \in SS^c} x_{ij} - \sum_{e \in S^cS} x_{ij} </math> | |||
En particular vale que <math> x_{ij} \leq c_{ij} </math> y <math> x_{ij} \geq b_{ij} </math>. Usando esto vale que : | |||
<br> <math> v \leq \sum_{e \in SS^c} c_{ij} - \sum_{e \in S^cS} b_{ij} </math> | |||
<br>d) | |||
<br>e) | |||
<br>f) | |||
==Ejercicio 11. | ==Ejercicio 11.27:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | |||
==Ejercicio 11.28:== | |||
[[Category: Prácticas]] |