Además, determine si el corte es mínimo.
1. P={a, d} para el ejercicio 1, sección 10.1
2. P={a, d, e} para el ejercicio 2, sección 10.1
3. P={a, b, c, d} para el ejercicio 3, sección 10.1
En los ejercicios 4 al 16, encuentre un corte mínimo en cada red.
4. Figura 10.1.1
5. Figura 10.1.4
6. Figura 10.1.5
7. Ejercicio 1, sección 10.1
8. Ejercicio 2, sección 10.1
9. Ejercicio 3, sección 10.1
10. Ejercicio 4, sección 10.1
11. Ejercicio 5, sección 10.1
12. Ejercicio 6, sección 10.1
13. Ejercicio 7, sección 10.1
14. Ejercicio 8, sección 10.1
15. Ejercicio 9, sección 10.1
16. Ejercicio 12, sección 10.2
Los ejercicios 17 al 22 se refieren a una red G que, además de tener capacidades enteras no negativas Cij, tiene requerimientos mínimos mijde flujo en enteros no negativos en las aristas. Esto es, un flujo F debe satisfacer
mij ≤ Fij ≤Cij
para todas las aristas (i, j).
17. Dé un ejemplo de una red G, en la que mij≤Cijpara todas las aristas (i, j) para las que no hay un flujo. Defina
m(P, P)−C(P, P) ≤ V ≤C(P, P)−m(P, P)
para cualquier cortadura (P, P ).
19. Demuestre que si existe un flujo en G, existe un flujo máximo en G con valor
20. Suponga que G tiene un flujo F. Desarrolle un algoritmo para encontrar un flujo máximo en G.
21. Demuestre que si existe un flujo en G, existe un flujo mínimo en G con valor máx{m(P, P )−C(P , P) | (P, P ) es un corte en G}.
22. Suponga que G tiene un flujo F. Desarrolle un algoritmo para encontrar un flujo mínimo en G.
23. ¿Falso o verdadero? Si F es un flujo en una red G y (P, P ) es un corte en G y la capacidad de (P, P ) excede el valor del flujo F, entonces el corte (P, P ) no es mínimo y el flujo F no es máximo. Si esto es verdadero, pruébelo; de otra manera, dé un contraejemplo.
Get 10.3.23 exercise solution
