Repetimos esta operación hasta marcar el drenaje. Si el flujo permanece sin etiquetar, entonces el flujo encontrado es máximo y el conjunto de arcos que conectan los vértices marcados con los no marcados forman un corte mínimo.

3. Deja que se etiquete el caldo. (j+, ε(t)), Entonces f(j,t) reemplazar con f(j,t)+ε(t). Si la acción está marcada (j-, ε(t)), Eso f(j,t) reemplazar con f(j,t)-ε(t). vamos a la cima j. Si j tiene una marca (yo+, ε(j)), luego reemplazamos f(yo,j) en f(i,j)+ε(t), y si (yo-, ε(j)), f(j,i) reemplazar con f(j,i)-ε(t). vamos a la cima i. Repetimos esta operación hasta llegar a la fuente. s. El cambio de flujo se detiene, se borran todas las marcas y se pasa al paso 2.

EJEMPLO 3.14.

M 4K

TAREA. Encuentra el flujo más alto de la red.

ALGORITMO

Denotemos el vértice s= x0. Todos los demás son x i.

Etapa 1.

1. Elija cualquier camino cuyos arcos no estén saturados.

2. Aumentamos la cantidad de flujo a lo largo de este camino en uno hasta que no quede ningún arco saturado en él.

Continuamos el proceso de aumentar el flujo hasta que se construye el flujo completo, es decir. cualquier camino contendrá al menos un arco saturado.

Etapa 2.

2. Si х i ya es un vértice marcado, entonces marcamos (+i) todos los vértices no etiquetados a los que van arcos insaturados desde х i, y con el índice (–i) todos los vértices no marcados desde donde van arcos con flujo distinto de cero a x i.

3. Si como resultado de este proceso se marca un vértice t, entonces entre s Y t hay un camino cuyos vértices están marcados con los números de los vértices anteriores. Aumentamos el flujo en todos los arcos de este camino en uno si, al pasar de s A t la orientación del arco coincide con la dirección del movimiento, y se reduce en uno si el arco tiene la orientación opuesta. Pasemos al paso 1.

4. Cuando la cima t es imposible marcar que el proceso ha terminado y el flujo resultante es el flujo más grande de la red.

NOTA. Puede pasar a la etapa 2 sin completar la primera etapa (ver ejemplo 3.16).

EJEMPLO 3.15.

9

SOLUCIÓN:

Se ha encontrado un flujo completo en una red de transporte determinada. Los arcos saturados están resaltados.

En esta red también puedes marcar el vértice final, y el resultado del marcado será el mismo. Al cambiar el flujo, obtenemos una red en la que es imposible marcar el vértice final, por lo que el flujo en ella es el mayor e igual a 10.

EJEMPLO 3.16.

8 2 1

Se encontró un flujo incompleto en una red de transporte determinada.

Marquemos la red y aumentemos el flujo en ella según el algoritmo. obtenemos

En esta red también puedes marcar el vértice final, y el resultado del marcado será el mismo. Al cambiar el flujo, obtenemos una red en la que es imposible marcar el vértice final, por lo que el flujo en ella es el mayor e igual a 6.

Sección IV. PROGRAMACIÓN DINÁMICA.

La programación dinámica se utiliza para encontrar soluciones óptimas de varias etapas. Por ejemplo, planificación a largo plazo para la sustitución de equipos; actividad de la industria durante varios años. Utiliza el principio de optimización, según el cual cualquier nueva solución parcial debe ser óptima en relación con el estado alcanzado.

Es mejor resolver uno muchas veces. tarea sencilla más de una vez complejo.

PROBLEMA 1. Sobre la ruta más ventajosa entre dos puntos.

Se requiere construir un camino que conecte dos puntos A y B, de los cuales el segundo se encuentra al noreste del primero. Para simplificar, digamos que trazar un camino consta de una serie de pasos, y en cada paso podemos movernos hacia el norte o hacia el este. Entonces, cualquier camino es una línea discontinua escalonada, cuyos segmentos son paralelos a uno de los ejes de coordenadas. Se conocen los costos de construcción de cada una de estas secciones.

EJEMPLO 4.1. Encuentre el camino mínimo de A a B.

El último paso es lograr T.V. Antes del último paso, podríamos estar en puntos desde donde podríamos llegar a la T.V. en un solo paso. Hay dos de esos puntos (el sistema podría estar en uno de dos estados). Para cada uno de ellos, solo hay una opción para llegar a T.V: para uno, moverse hacia el este; por el otro, al norte. Escribimos los costos 4 y 3 en cada caso.

4

Ahora optimicemos el penúltimo paso. Tras el paso anterior, podríamos acabar en uno de tres puntos: C 1, C 2, C 3.

Para el punto C 1, solo hay un control (marquémoslo con una flecha): muévase hacia el este y los costos serán 2 (en este paso) + 4 (en el siguiente paso) = 6. De manera similar, para el ítem C 3 los costos serán 2+3=5. Para t.C 2 hay dos controles: ir al este o al norte. En el primer caso, los costes serán 3+3=6, y en el segundo caso – 1+4=5. Esto significa que el control óptimo condicional es ir hacia el norte. Marquémoslo con una flecha e ingresemos los costos correspondientes.

Respuesta: x1 =1; x3 =0; x3 =4; Ancho=3,5

ALGORITMO GENERALIZADO

1. Describe el sistema. Es decir, averiguar qué parámetros caracterizan el estado del sistema controlado antes de cada paso. Es importante poder plantear la tarea de forma correcta y “modesta”, sin sobrecargarla con detalles innecesarios, simplificando al máximo la descripción del sistema controlado.

2. Divida la operación en pasos (etapas). Aquí deben tenerse en cuenta todas las restricciones razonables impuestas a la gestión. El paso debe ser lo suficientemente pequeño para que el procedimiento de optimización del control de pasos sea bastante simple; y el paso, al mismo tiempo, no debe ser demasiado pequeño para no realizar cálculos innecesarios que compliquen el procedimiento para encontrar la solución óptima, pero que no conduzcan a un cambio significativo en el óptimo. función objetivo.

3. Descubra el conjunto de controles de paso x i para cada paso y las restricciones impuestas a ellos.

4. Determine qué ganancia aporta el control x i en el paso i, si antes el sistema estaba en el estado S, es decir escriba las funciones de pago:

w yo = f yo (S, x yo)

5. Determine cómo cambia el estado del sistema bajo la influencia del control x i en 1er paso, es decir. escribir funciones de cambio de estado.

S / =φ yo (S, x yo)

6. Escriba la ecuación principal de programación dinámica recurrente, expresando la ganancia óptima condicional a través de una función ya conocida.

W i (S)= máx(f i (S, x i)+W i+1 (φ i (S, x i)))

7. producir optimización condicional el último paso, haciendo varias suposiciones sobre cómo terminó el penúltimo paso, y para cada una de estas suposiciones encuentre el control óptimo condicional (seleccionado en función de la condición de que el paso terminó con algo) en el último paso.

W m (S)= máx(f m (S, x m))

8. Realice la optimización condicional, comenzando desde el penúltimo paso y terminando con el primer paso (retroceder).

9. producir optimización incondicional control, “leyendo” las recomendaciones correspondientes en cada paso: tomar el control óptimo encontrado en el primer paso y cambiar el estado del sistema, para el estado encontrado encontrar el control óptimo en el segundo paso, etc. hasta el último paso.

PRINCIPIO DE OPTIMALIDAD. Cualquiera que sea el estado del sistema antes del siguiente paso, es necesario elegir el control en este paso de modo que la ganancia en este paso más la ganancia óptima en todos los pasos posteriores sea máxima.

El principio de programación dinámica no implica que cada paso se optimice por separado, independientemente de los demás. ¿Qué sentido tiene elegir un control cuya efectividad sea máxima en un paso específico, si este paso nos privará de la oportunidad de ganar bien en los pasos siguientes?

En la práctica, hay casos en los que una operación debe planificarse por un período de tiempo indefinidamente largo. El modelo para tal caso es un proceso controlado de infinitos pasos, donde todos los pasos son iguales. Aquí la función ganadora y la función de cambio de estado no dependen del número de paso.

Sección V. MODELADO DE SIMULACIÓN

La idea de este algoritmo es encontrar rutas de un extremo a otro con flujos positivos desde el origen hasta el sumidero.

Considere una arista (i, j) con capacidad (inicial). Durante la ejecución del algoritmo, parte de esta capacidad es "quitada" por los flujos que pasan a través de un borde determinado, como resultado, cada borde tendrá una capacidad residual. Escritura: ancho de banda residual. Una red en la que todos los bordes tienen capacidad residual se llamará residual.

Para un nodo arbitrario j que recibe un flujo del nodo i, definimos una etiqueta, donde es el valor del flujo que fluye del nodo j al nodo i. Para encontrar el caudal máximo, realizamos los siguientes pasos.

Para todos los bordes, establecemos la capacidad residual igual a la capacidad inicial, es decir equiparemos =. Asignemos y marquemos el nodo 1 con una etiqueta. Suponemos i=1.

El conjunto de nodos j al que se puede ir desde el nodo I a lo largo de una arista con una capacidad residual positiva >0 para todo j. Si, realizamos la etapa 3, en caso contrario pasamos a la 4.

En encontramos el nodo k tal que. Coloquemos y marquemos el nodo k con una etiqueta. Si k=n, se encuentra una ruta de un extremo a otro y pasamos a la etapa 5; de lo contrario, configuramos i=k y volvemos a la etapa 2.

Revertir. Si i = 1, no es posible una ruta de un extremo a otro y vamos a 6. Si, encontramos el nodo r etiquetado que precede inmediatamente al nodo i y lo eliminamos del conjunto de nodos adyacentes al nodo r. Establecemos i=r y volvemos a la etapa 2.

Definición de una red residual. Denotemos por el conjunto de nodos a través de los cuales pasa la p_ésima ruta de extremo a extremo encontrada desde el nodo de origen (nodo 1) hasta el nodo sumidero (nodo n). Luego, el flujo máximo que pasa a lo largo de esta ruta.

La capacidad residual de los bordes que forman el camino de un extremo a otro disminuye en una cantidad en la dirección del flujo y aumenta en la misma cantidad en la dirección opuesta.

Eso. para un borde (i, j) incluido en una ruta de extremo a extremo, las capacidades residuales actuales cambian:

1) si el flujo va del nodo i al j,

2) si el flujo va del nodo j al i.

a) con m caminos de extremo a extremo encontrados, el flujo máximo se expresa por

b) Teniendo los valores de las capacidades inicial y final del borde (i, j), podemos calcular el flujo óptimo por este borde de la siguiente manera. Digámoslo. Si >0, el flujo que pasa por el borde (i, j) es igual. Si >0, entonces el flujo es igual. (el caso en el que tanto >0 como >0 son imposibles).

Ejemplo 1. Encuentre el flujo máximo en la red Fig. 1

Iteración 1. =

3) k=3, desde entonces. Asignamos y marcamos el nodo 3 con una etiqueta. i=3 y volver a 2)

5) k=5 y. Marcamos el nodo 5 con una etiqueta. Obtenemos un camino de paso.

6) determinamos la ruta de un extremo a otro mediante etiquetas, comenzando desde el nodo 5 y terminando en el nodo 1: . Y. Calculamos las capacidades residuales a lo largo del camino:

Iteración 2.

1) y marque el nodo 1 con una etiqueta. yo=1

2") (por lo que el nodo 5 no está incluido en

3") k=4, y marque el nodo 4 con una etiqueta. i=4 y volver a 2)

2""") (dado que los nodos 1 y 3 están marcados, no están incluidos)

3""") k=5 y. Marcamos el nodo 5 con una etiqueta. Se obtiene un camino de un extremo a otro. Ir a 5)

Iteración 3.

1) y marque el nodo 1 con una etiqueta. yo=1

3) k = 2 y marque el nodo 2 con una etiqueta. i=2 y volver a 2)

3") k=3 y. Marcar el nodo 3 con una etiqueta. i=3 y volver a 2)

2") (desde) vaya a 4)

4) la etiqueta del nodo 3 muestra el número del nodo anterior. En esta iteración, el nodo 3 no se tiene en cuenta en el futuro; su etiqueta está tachada. y volver a 2)

2""") (ya que el nodo 3 se elimina de la posible ruta de un extremo a otro)

3""") y. Marcamos el nodo 5 con una etiqueta. Se obtiene un camino de un extremo a otro. Ir a 5)

5) yo. Calculamos las capacidades residuales a lo largo del camino:

Iteración 4. En esta iteración, la ruta con

Iteración 5. En esta iteración, la ruta con

Iteración 6: No son posibles nuevas rutas de un extremo a otro porque todos los bordes que se originan en el nodo 1 tienen capacidad residual cero. Vaya a 6) para determinar la solución.

6) el volumen máximo de flujo en la red es igual a unidades.

Los valores de flujo a lo largo de varios bordes se calculan restando los últimos valores de capacidad residual de los valores de capacidad iniciales.

Resultados del cálculo: tabla. 1

Ejecución gráfica secuencial del algoritmo para encontrar el caudal máximo (ejemplo 1)

e) f) No existen caminos de paso

Arroz.

Los datos iniciales sobre el sistema de transporte, por ejemplo, en planta, se muestran en la Fig. 2, también se puede especificar mediante una tabla (Tabla 2).

Tabla 2. Datos iniciales para el problema de flujo máximo.

Evidentemente, la capacidad máxima del sistema de transporte no supera 6, ya que no se pueden enviar más de 6 unidades de carga desde el punto de partida 0, es decir, 2 unidades al punto 1, 3 unidades al punto 2 y 1 unidad al punto 3. A continuación, es necesario asegurarse de que las 6 unidades de carga que salieron del punto 0 lleguen al punto final 4. Obviamente, 2 unidades de carga que llegaron al punto 1 se pueden enviar directamente al punto 4. La carga que llegó al punto 2 lo hará. deben dividirse: 2 unidades se envían inmediatamente al punto 4 y 1 unidad al punto intermedio 3 (debido a la capacidad limitada del tramo entre los puntos 2 y 4). Al punto 3 se entregó la siguiente carga: 1 unidad desde el punto 0 y 1 unidad desde el punto 3. Las enviamos al punto 4. Entonces, el rendimiento máximo del sistema de transporte en cuestión es de 6 unidades de carga. En este caso, las secciones internas (ramas) entre los puntos 1 y 2, así como entre los puntos 1 y 3, no se utilizan. La rama entre los puntos 1 y 4 no está completamente cargada: se envían 2 unidades de carga junto con ella. un rendimiento de 3 unidades. La solución se puede presentar en forma de tabla (Tabla 3)

Tabla 3. Resolviendo el problema del flujo máximo

Problema de programación lineal para maximización de flujo. Formulemos el problema de flujo máximo en términos de programación lineal. Sea X KM el volumen de transporte desde el punto K al punto M. Según la Fig. 2 K = 0,1,2,3, M = 1,2,3,4 y el transporte sólo es posible hasta el punto con un número mayor. Esto significa que hay un total de 9 variables X KM, a saber, X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. El problema de programación lineal destinado a maximizar la el flujo tiene la forma:

X 01 + X 02 + X 03 = F (0)

X01 + X12 + X13 + X14 = 0 (1)

X02 - X12 + X23 + X24 = 0 (2)

X 03 - X 13 - X 23 + X 34 = 0 (3)

X 14 - X 24 - X 34 = - F (4)

¿X KM? 0, K, M = 0, 1, 2, 3, 4

Aquí F es la función objetivo, la condición (0) describe el ingreso de mercancías al sistema de transporte. Las condiciones (1) - (3) establecen las relaciones de equilibrio para los nodos 1-3 del sistema. En otras palabras, para cada uno de los nodos internos, el flujo entrante de bienes es igual al flujo saliente; los bienes no se acumulan dentro del sistema y no “nacen” en él. La condición (4) es la condición para la "salida" de cargas del sistema. Junto con la condición (0), constituye una relación de equilibrio para el sistema en su conjunto (“entrada” es igual a “salida”). Las siguientes nueve desigualdades establecen restricciones a la capacidad de las “ramas” individuales del sistema de transporte. Luego se indica la no negatividad de los volúmenes de tráfico y la función objetivo. Está claro que la última desigualdad se deriva de la forma de la función objetivo (relación (0) o (4)) y de la no negatividad de los volúmenes de tráfico. Sin embargo, la última desigualdad conlleva algunas información general- A través del sistema se puede pasar un volumen de carga positivo, o cero (por ejemplo, si hay movimiento en círculo dentro del sistema), pero no negativo (no tiene sentido económico, pero sí formal). modelo matemático“no sabe” sobre esto).

A la hora de planificar la distribución racional de productos en la red de distribución, es necesario coordinar la capacidad del canal con las necesidades de los clientes y con la capacidad de la planta de producción. Esta clase de problemas se resuelve encontrando el flujo máximo.

Consideremos una red de distribución (Fig. 4.21), en la que los puntos 0 (entrada, por ejemplo, al almacén de productos terminados de un fabricante) y norte (salida, centros de distribución, almacenes de organizaciones mayoristas y minoristas, consumidores) y puntos de conexión de cada arco (segmento) i Y j, el número dij > 0 está asociado, llamado rendimiento arcos. El valor de rendimiento caracteriza el máximo cantidad permitida Flujo de material que puede pasar a lo largo del arco correspondiente por unidad de tiempo.

Arroz. 4.21.

La cantidad de productos que pasan a lo largo de un arco desde i a j , lo llamaremos flujo a lo largo de un arco ( i ,j ) y denotado por . Es obvio que

Si tenemos en cuenta que todo el flujo de material que entra por el punto intermedio de la red debe salir completamente de él, obtenemos

Del requisito natural de igualdad de flujos en la entrada y en la salida tenemos

Llamaremos al valor de Z el valor del flujo en la red y plantearemos el problema de maximizar Z sujeto a las condiciones anteriores.

Encontrar el flujo máximo se reduce a encontrar el rendimiento del corte mínimo.

Consideremos un algoritmo de búsqueda universal en forma matricial.

La etapa inicial del algoritmo consiste en construir una matriz. D 0, en el que se ingresan los valores de rendimiento (para un arco no orientado tomamos los valores simétricos de los elementos de la matriz).

Los pasos principales del algoritmo son encontrar un camino determinado y corregir el flujo a lo largo de este camino.

Al encontrar un camino, utilizamos un proceso de marcado. Marcamos con el símbolo * la fila y columna cero de la matriz (entrada de red). En la línea 0 que buscamos, marcamos las columnas correspondientes con índices

y mueva las etiquetas de las columnas a las filas. Luego tomamos la i-ésima fila marcada, buscamos una columna sin marcar con , con la que hacemos coincidir las etiquetas de índice

Transferimos las etiquetas de las columnas a las filas y continuamos este proceso hasta marcar la enésima columna.

Entonces " marcha atrás"Utilizando los índices, descubrimos el camino que condujo al η-ésimo vértice, reducimos la capacidad de los arcos del camino (elementos de la matriz) en V n y aumentar los elementos simétricos en la misma cantidad.

Este procedimiento continúa hasta la marca. norte -Las cimas no se volverán imposibles.

El flujo máximo se puede encontrar restando de la matriz original D 0, obtenido después de la corrección anterior de la matriz de capacidad:

Ejemplo 4.4

La producción se encuentra en Moscú. Para distribuir productos, la empresa atrae intermediarios que trabajan con la empresa a través de centros de distribución en varios niveles. En la parte europea de Rusia hay una empresa mayorista 1, atendida por un centro de distribución central. La empresa mayorista 2 opera en el extranjero cercano (Ucrania, Bielorrusia) y cuenta con el servicio de un centro de distribución regional. La empresa tiene sus propios clientes en el mercado local (Moscú y región de Moscú): minoristas que reciben los productos del centro de distribución de la ciudad. Los centros de distribución regionales y urbanos se reabastecen desde el centro de distribución central.

Destaquemos un fragmento de la red de distribución:

• almacén de productos terminados de una empresa manufacturera;
• centro de distribución central;
• centro de distribución regional;
• centro de distribución de la ciudad;
• dos empresas mayoristas;
• punto de venta minorista propiedad de la empresa;
• consumidores.

Arroz. 4.22.

Designemos cada enlace de la red de distribución con un número y pongamos la capacidad encima de los arcos. La capacidad de rendimiento, según el tipo de enlace, se puede expresar en términos del volumen de capacidad de producción, la necesidad (demanda) planificada de los consumidores y la capacidad del mercado.

El gráfico de la red de distribución de productos se muestra en la Fig. 4.23. Construyamos una matriz D 0, en el que ingresamos los valores de las capacidades de rendimiento de los enlaces de la red de distribución (Fig. 4.24).

Arroz. 4.23.

Arroz. 4.24.

Desde la fila cero marcamos los vértices (filas-columnas) 1, 2 y 3 con índices μ = 0 y V, igual a 30,10 y 10.

Desde la línea marcada 1, marque los vértices 4 y 5 con índices μ = 1 y V4 = min (30,15) = 15, V5 = min (30,10) = 10.

Desde la línea 3 marcamos el vértice 6 y, finalmente, desde la línea 4 – el vértice 7 (Fig. 4.25).

Arroz. 4.25.

Regresando por μ encontramos el camino: al vértice 7 desde 4, al vértice 4 desde 1, al vértice 1 desde 0; elementos de ajuste D 0 por valor de caudal V7 = 15.

El siguiente paso da un camino con flujo 5 (Fig. 4.26).

Arroz. 4.26.

El siguiente paso da el resultado que se muestra en la Fig. 4.27.

Arroz. 4.27.

No es posible realizar más marcas. De aquí obtenemos la matriz de flujo máximo (Fig. 4.28).

Arroz. 4.28.

Como resultado de aplicar el algoritmo para encontrar el flujo máximo en la red, los resultados presentados en la Fig. 4.29. Los pares de números entre paréntesis que se muestran en los arcos del gráfico indican el rendimiento máximo del arco y el volumen recomendado de bienes suministrados a la red.

Suma de flujos a través de arcos incidentes. v, es igual a la suma de los flujos a través de los arcos incidentes w; esta suma se llama valor de flujo. Nos interesarán principalmente los flujos que tengan el mayor valor posible: los llamados flujos máximos. EN caso general Una red puede tener varios caudales máximos diferentes, pero sus valores deben ser los mismos. (4)

El estudio de los flujos máximos a través de una red N = (V,D,a) está estrechamente relacionado con el concepto de corte, es decir tal conjunto A de arcos de un dígrafo D que tiene la propiedad de que cualquier cadena simple de v V pasa por el arco perteneciente a A. La capacidad de un corte es la suma de las capacidades de los arcos que le pertenecen. Los cortes que tienen el menor rendimiento posible se denominan cortes mínimos.

La magnitud de cualquier flujo no excede la capacidad de rendimiento de ningún corte y, por lo tanto, la magnitud de cualquier flujo máximo no excede el rendimiento de ningún corte mínimo. Sin embargo, no está inmediatamente claro que los dos últimos números siempre iguales entre sí; Este resultado fue obtenido por los matemáticos estadounidenses Ford y Fulkerson en 1955 y lo denominaron teorema de flujo máximo y corte mínimo.

Teorema (sobre flujo máximo y corte mínimo). En cualquier red, el tamaño de cualquier flujo máximo es igual a la capacidad de cualquier corte mínimo.

El teorema de flujo máximo y corte mínimo le permite verificar si un flujo dado es máximo o no, pero solo para redes bastante simples. Por supuesto, en la práctica tenemos que lidiar con redes grandes y complejas y, en general, es difícil encontrar el flujo máximo mediante una simple selección. Describamos un algoritmo para encontrar el flujo máximo en cualquier red con rendimiento entero.

Paso 1. Primero, seleccionemos un flujo que tenga un valor distinto de cero (si dicho flujo existe). Por ejemplo, si N es la red que se muestra en la Fig. 29.3, entonces el flujo que se muestra en la Fig. 29.4. Cabe destacar que cuanto mayor sea el valor del flujo inicial que hayamos elegido, más sencillos serán los pasos posteriores.

Paso 2. Con base en N, construimos una nueva red N’ cambiando la dirección del flujo al opuesto. Más precisamente, cualquier arco a para el cual (a) = 0 permanece en N' con su capacidad original, y cualquier arco a para el cual , es reemplazado por un arco a con capacidad y un arco opuesto con capacidad (a). La red N' en nuestro ejemplo se muestra en la Fig. 29.5. Vértice v Ya no es una fuente, sino un sumidero.

Paso 3. Si en la red N’ podemos encontrar un flujo distinto de cero desde v c, entonces se puede agregar al flujo original y obtener un nuevo flujo de mayor valor en N. Ahora puedes repetir el paso 2, usando el nuevo hilo N' en lugar de N' al construir la red. Repitiendo este procedimiento, eventualmente llegaremos a una red N' que no contiene flujos distintos de cero; entonces el caudal correspondiente será el caudal máximo. Por ejemplo, en la Fig. 29.5 hay un flujo distinto de cero en el que fluye a través de los arcos ( v,u), (u,z), (z,x), (x, y) Y ( y,) son iguales a uno, y los flujos a través de los arcos restantes son iguales a cero. Sumando este flujo al flujo de la Fig. 29.4, obtenemos el flujo que se muestra en la Fig. 29,6; Repitiendo el paso 2, es fácil demostrar que este es el flujo máximo.

Literatura utilizada:

(1) http://pgap.chat.ru/zap/zap264.htm#0

(2) Asanov M.O., Baransky V.A., Rasin V.V. Matemáticas discretas: gráficos matroides, algoritmos

(3) Basaker R., Saati T. Gráficos y redes finitos.

(4) Wilson R. Introducción a la teoría de grafos