Ingenieria

Algoritmo de flujo máximo.
Definición.
Es aquel que viaja desde un único lugar de origen hacia un único lugar de destino a través de arcos que conectan nodos intermediarios. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al destino la mayor cantidad posible de flujo
Definiciones básicas.
Flujo. Es el envio o circulación de unidades homogéneas de algúnproducto o sustancia que atraviesan la superficie en una unidad de tiempo.
Capacidad de flujo. Es la cantidad máxima que puede ingresar a través del nodo o fuente y salir por el nodo de destino.
Origen o fuente de flujo. Es el nodo por el cual el flujo ingresa
Destino sumidero, o vertedero de flujo. Es el nodo por el cual el flujo sale.
Capacidades residuales. Son las capacidades restantes delarco una vez pasados por el.
Usos del algoritmo del flujo máximo.
Este algoritmo se usa para reducir los embotellamientos en ciertos puntos de partida y destino en una red. Por ejemplo:
Sistemas de vías públicas.
Transporte de petróleo desde la refinería hasta diversos centros de almacenamiento.
Distribución de energía eléctrica a través de una red de alumbrado pública.
Tenemos el conocidoproblema de flujo máximo o maximal: ¿cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero sin violar ninguna restricción de capacidad?
En otras palabras, el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.
El procedimiento para obtener el flujo máximo de una red, consiste enseleccionar repetidas veces cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria.
En algunas redes circula por los arcos un flujo (envío o circulación de unidades homogéneas de algún producto: automóviles en una red de carreteras, litros de petróleo en un oleoducto, bits por un cable de fibra óptica) desde el origen o fuente al destino, tambiéndenominado sumidero o vertedero. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:
* El flujo es siempre positivo y con unidades enteras.
* El flujo a través de un arco es menor o igual que la capacidad.
* El flujo que entra en un nodo es igual al que sale de él.
Algoritmo deFord-Fulkerson.
Propone buscar caminos en los que se pueda aumentar el flujo, hasta que alcance el flujo máximo.
La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos de origen y destino.

FLUJO MÁXIMO:
En una red G, el flujo máximo es un flujo máximo. Generalmente existen varios flujos con el mismo valor máximo. Para encontrar el flujo máximo consideraremos un flujoinicial en cada arista igual a cero, después se determina un camino específico de la fuente al sumidero y se incrementa el flujo.
Si una arista esta dirigida hacia la fuente decimos que esta arista esta dirigida en forma impropia, en caso contrario esta dirigida en forma propia.
Si se determina un camino P de la fuente al sumidero en donde cada arista de P esta orientada en forma propia y elflujo en cada arista es menor que la capacidad de la arista, es posible aumentar el valor de flujo.
Es posible incrementar el flujo en ciertos caminos de la fuente al sumidero que tenga aristas orientadas en forma impropia y propia. Sea P un camino de “a” a “z” y sea “x” un vértice en P que no sea “a” ni ”z”
Ambas aristas están orientadas en forma propia, en este caso, si incrementamos el flujo en", el flujo en la entrada en x seguirá siendo igual al flujo de salida de x.
Si incrementamos el flujo en e2 en ", debemos disminuir el flujo en e1 en " de modo que el flujo de entrada en x siga siendo igual al flujo de salida en x.
Es análogo en el caso b
Disminuimos el flujo en ambas aristas en ". En cada caso las asignaciones resultantes de las aristas dan como resultado un flujo....