13.7: Ejercicios

1. Considere el diagrama de red en la Figura 13.14. Para cada borde dirigido, el primer número es la capacidad y el segundo valor está destinado a dar un flujo\(ϕ\) en la red. Sin embargo, el flujo sugerido no es válido

a. Identificar el motivo (s) no\(ϕ\) es válido (s).

b. sin cambiar ninguna de las capacidades de borde, modificar\(ϕ\) en un flujo válido\(\hat{ϕ}\). Trate de utilizar el menor número posible de modificaciones.

Figura 13.14. Un flujo no válido en una red

2. Alice afirma haber encontrado un flujo de red (válido) de valor 20 en la red que se muestra en la Figura 13.15. Bob le dice que no hay manera de que tenga razón, ya que ningún flujo tiene un valor mayor a 18. ¿Quién tiene razón y por qué?

Figura 13.15. Una red

3. Encuentre una ruta de aumento\(P\) con al menos un borde hacia atrás para el flujo\(ϕ\) en la red que se muestra en la Figura 13.16. ¿Cuál es el valor de\(δ\) para\(P\)? Llevar a cabo una actualización de\(ϕ\) uso\(P\) para obtener un nuevo flujo\(\hat{ϕ}\). ¿Cuál es el valor de\(\hat{ϕ}\)?

Figura 13.16. Una red con flujo

4. Demostrar Proposición 13.7. Deberá verificar que las leyes de conservación de flujo se mantengan en cada vértice a lo largo de un camino de aumento (que no sea\(S\) y\(T\)). Hay cuatro casos a considerar dependiendo del estado de adelante/atrás de los dos bordes en el camino de aumento que son incidentes con el vértice.

5. Encuentra la capacidad del corte\((L,U)\) con

\(L=\{S,F,H,C,B,G,I\}\)y\(U=\{A,D,E,T\}\)

en la red que se muestra en la Figura 13.16.

6. Encuentra la capacidad del corte\((L,U)\) con

\(L=\{S,F,D,B,A\}\)y\(U=\{H,C,I,G,E,T\}\)

en la red que se muestra en la Figura 13.16.

7. Para cada una de las rutas de aumento\(P_1, P_2, P_3\), y\(P_4\) en el Ejemplo 13.8, actualice el flujo en la Figura 13.2. (Tenga en cuenta que su solución a este ejercicio debe consistir en cuatro flujos de red. No intente usar las cuatro rutas en secuencia para crear un flujo de red actualizado).

8. Continuar ejecutando el algoritmo de etiquetado Ford-Fulkerson en el flujo de red en la Figura 13.12 hasta que el algoritmo se detenga sin etiquetar el sumidero. Encuentra el valor del flujo máximo así como un corte de capacidad mínima.

9. Utilice el algoritmo de etiquetado Ford-Fulkerson para encontrar un flujo máximo y un corte mínimo en la red que se muestra en la Figura 13.17 comenzando desde el flujo de corriente que se muestra allí.

Figura 13.17. Una red con flujo

10. La Figura 13.18 muestra una red. Partiendo del flujo cero, es decir, el flujo con algoritmo de etiquetado\(ϕ(e)=0\) for every directed edge \(e\) in the network, use the Ford- Fulkerson para encontrar un flujo máximo y un corte mínimo en esta red.

Figura 13.18. Una red

11. Consideremos una red en la que la fuente S tenga precisamente tres vecinos:\(B, E\), y\(F\). Supongamos también eso\(c(S,B)=30, c(S,E)=20\), y\(c(S,F)=25\). Sabes que hay un flujo\(ϕ\) en la red pero no sabes cuánto flujo hay en cualquier borde. Usted sabe, sin embargo, que cuando el algoritmo de etiquetado Ford-Fulkerson se ejecuta en la red con flujo de corriente\(ϕ\), los dos primeros vértices etiquetados son\(S\) con etiqueta\((∗,+,∞)\) y\(F\) con etiqueta\((S,+,15)\). Utilice esta información para determinar el valor del flujo\(ϕ\) y explicar cómo lo hace.