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 194: | Línea 194: | ||
<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) |