Algoritmo de flujo máximo

Si os cuesta entenderlo ayuda imaginarlo como tuberías con distinto caudal. La tubería que va de A a C tiene un caudal de 7, pero como la tubería que va de C a F solo tiene un caudal de 4, la tubería inicial mandará la máxima capacidad (4) y se quedará con la resta (3). La siguiente tubería, como tiene el máximo porque la tubería anterior era mayor, quedará a 0. Y así con todo.

Uno de los mejores profesores de platzi, se le da muy bien explicar

Algoritmo de flujo máximo: Encontrar el camino de un punto A a un punto B con la mayor cantidad de flujo.

• 1: Establecer un grafo dirigido.
• 2: establecemos todos los vértices en 0
• 3: establecer caminos desde el punto A hasta el punto B.
• 4: encontramos la conexión con menor capacidad, pues ésta es quien le dice al camino la capacidad máxima.
• 5: Hacemos esta iteración hasta que no hayan más caminos.
• 6: De cada ruta obtenemos un flujo, sumando todos los flujos obtendremos el flujo máximo.

Los algoritmos de flujo máximo se aplican a la vida cotidiana para resolver problemas de gestión de recursos, reparto en empresas de logística, control de vuelos con escalas en aerolíneas, gestión de selección de proyectos o para calcular las intensidades máximas en un circuito eléctrico, programación, entre otros.

El curso es excelente, simple y conciso. Solo tengo una pequeña corrección, no hay que confundir un grafo ponderado con un árbol de expansión. El hecho de que tenga aristas relacionadas a un valor lo convierte en un grafo ponderado. Un árbol de expansión es un grafo con todos los vértices de un grafo no dirigido, sin contener todas las aristas, sino un subconjunto de ellas, manteniendo la conexidad del grafo.

El camino 1 deberia ser A,C, E, G porque es el que mas flujo tiene.

Algoritmo de flujo máximo
Permite hallar el flujo máximo (valor máximo a enviar) entre dos puntos de un grafo dirigido y ponderado, donde cada valor representa el máximo flujo que puede pasar a través de la conexión.
Pasos:

• Asignar un valor de cero a cada nodo
• Elegir un camino por el que se pueda llegar al nodo destino, de preferencia por el que se pueda enviar mayor flujo. Este estará limitado por la arista de menor valor
• Actualizar los valores de la arista colocando el flujo que aún pueden recibir y los nodos con el valor de flujo que recibieron.
• Iterar con otro camino hasta que ya no existan más caminos posibles (ya no se pude pasar por aristas de valor cero)

No entiendo el paso 3 de escoger el menor Flujo, acaso el objetivo no es encontrar el flujo mayor? Porque escogeriamos el menor flujo? En que nos beneficia?

El algoritmo de flujo màximo, busca en los grafos dirigidos, encontrar el flujo máximo en estos.

El grafo tiene que ser dirigido, si no lo es, entonces tienes que dirigir cada conexión.

¿por qué un cuarto camino no pudo ser ACDEG habiendo una disponibilidad de 2?

Excelente tema y muy bien explicado

Primero debemos identificar todas las rutas, y después calcular cuál de estas tiene el flujo máximo

En el Camino 4 Vertice “E” quedan 2 pero porque se le restan al 4 que ya tenia

nice

Pregunta… si al definir el camino ACEG con un valor mínimo de 2, el profe restó de A ( 3-2 = 1) ¿por qué al entrar a C no sumó esas 2 a 4 para que a C entraran 6 para que así 4 fueran a F y 2 a E?

Serviría para medir la capacidad máxima de flujo en vías.

Ejercicio demostrativo de Algoritmo de flujo máximo

1) Buscar siempre el mayor flujo

Genial este algoritmo.

A LP can Max Z
s.a
Restrictions
Generates a solution

Este curso tiene demasiada información para procesarla.

En la segunda pongo los números del color del camino que toma. Espero y se llegue a entender.
En el de abajo a la derecha puse cómo quedarían los flujos que sobrarían y en el último puse los flujos que se utilizaron.

En conclusión, de las 17 unidades que podrían salir de “a”, sólo podemos enviar 13 hasta “g”.

Excelente!

Gracias Profe Sergio

Muy bueno!

Pensé que este sería el algoritmo más fácil pero me parece complicado 😕

Pragmático.

con lo que me quedo:

• Se debe enviar lo máximo en cada camino en función de lo que va quedando (hace falta)
• En el grafo final podemos ver los flujos que llegan a cada vértice
• Lo que logra enviarse desde el nodo inicial debe se igual a lo que llega en el nodo final