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 148: | Línea 148: | ||
<br> | <br> | ||
El problema es complejo y se llama "Maximum Flows with Edge Demands". Pueden encontrar una explicación detallada en: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/25-maxflowext.pdf | El problema es complejo y se llama "Maximum Flows with Edge Demands". Pueden encontrar una explicación detallada en: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/25-maxflowext.pdf | ||
==Ejercicio 11.16:== | ==Ejercicio 11.16:== | ||
Línea 189: | Línea 189: | ||
==Ejercicio 11.23:== | ==Ejercicio 11.23:== | ||
==Ejercicio 11.24:== | ==Ejercicio 11.24:== | ||
<br>a) | <br>a) | ||
<br>b) | <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) |