Teorema de flujo máximo

Teorema de Flujo Máximo:
Consiste en encontrar la cantidad máxima de flujo total que puede circular a través de la red en una unidad de tiempo. Para encontrar el flujo máximo consideraremos unflujo inicial en cada arista igual a cero, después se determina un camino específico de la fuente al sumidero y se incrementa el flujo.
Paso para realizar en Flujo Máximo.
1. Encontrar un camino quevaya desde el origen hasta el destino y que sus arcos tengan de flujo mayor a cero.
2. Encontrar en arco de menor capacidad de flujo del camino seleccionado en el paso anterior.
3. Para el caminoelegido, reducir la capacidad de flujo del arco menor a cada arco involucrado en el camino.
4. Repetir o través los pasos desde el Nº 1.
Redes de flujo de costo mínimo.
El modelo determina los flujos enlos diferentes arcos que minimizan el costo total al mismo tiempo que satisfacen las restricciones del flujo en los arcos y las cantidades de la oferta y la demanda en los nodos.
Problema del flujode costo mínimo.
1. La red es una red dirigida conexa.
2. Al menos uno de los nodos es nodo fuente.
3. Al menos uno de los nodos es nodo sumideros.
4. El resto de los nodos son nodos de trasbordo.5. Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco.
6. La red tiene suficientes arcos comosuficiente capacidad para permitir que todos los flujos generados por los nodos fuente lleguen a los nodos sumideros.
Cabe destacar que el flujo de costo mínimo se realizar por varios métodos, peroel que se va a utiliza es el Algoritmo de Dijkstra, que consiste en la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista.
Ejemplo:Utilizando el Algoritmo de Dijkstra queda de la siguiente manera:









Ejemplo de Flujo Máximo:











Se suman cada uno de los números que se tomó...