FLUJO MÁXIMO - ALGORITMO DE FORD-FULKERSON

  

la teoría de grafos, una red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente, al que se le asocia un flujo positivo y otro llamado sumidero que tiene un flujo negativo y a cada arista se le asocia cierta capacidad positiva. En cada vértice diferente a los dos especiales se mantiene la ley de corriente de kirchoff, en donde la suma de flujos entrantes  a un vértice debe ser igual a la suma de flujos que salen de él. Puede ser utilizada para modelar el trafico en un sistema de autopistas, fluidos viajando en tuberías, corrientes electricas en circuitos eléctricos o sistemas similares por lo que viaje algo entre modos.
Tenemos el conocido problema de flujo máximo o maximal: ¿Cual 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 posible en esa trayectoria.Podemos, mediante el algoritmo de Ford-Fulkerson, encontrar el flujo máximo de una red.

CAMINO MAS CORTO

En la teoría de grafos, el problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima. Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representan las ciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas. 

El problema es también conocido como el problema de los caminos más cortos entre dos nodos, para diferenciarlo de la siguiente generalización:

·   El problema de los caminos más cortos desde un origen en el cual tenemos que encontrar los caminos más cortos de un vértice origen v a todos los demás vértices del grafo.

·   El problema de los caminos más cortos con un destino en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.

·   El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v , v') en el grafo.