2357768

Redes teorema de flujo máximo teorema de flujo mínimo pareos y redes de Petri
Definición: Una Red es una gráfica dirigida, simple, con pesos y que debe cumplir las siguientes:

• Poseer unafuente o vértice fijo que no tiene aristas de entrada.
• Poseer un sumidero o vértice fijo que no tiene arista de salida
• El peso Cij de la arista dirigida de i a j llamado capacidad de “ij” esun número no negativo.

Una red de transporte es una gráfica dirigida, simple con pesos que satisface:

a) Un vértice fijo, designado como el origen o fuente, no tiene aristas de entrada.b) Un vértice, designado como destino o sumidero, no tiene aristas salientes.
c) El peso Cij de la arista dirigida (i, j) llamada capacidad de (i, j) es un número no negativo.


Flujomáximo
Se puede considerar un grafo como una red de flujo. Donde un nodo fuente produce o introduce en la red cierta cantidad de algún tipo de material, y un nodo sumidero lo consume. Cada arco, portanto, puede considerarse como un conducto que tiene cierta capacidad de flujo.
Una red de flujo es un grafo dirigido G=(V,E) donde cada arco (u,v) perteneciente a E tiene una capacidad no negativa.Se distinguen dos nodos: la fuente o nodo s, y el sumidero o nodo t. Si existen múltiples fuentes y sumideros, el problema se puede simplificar añadiendo una fuente común y un sumidero común.Este algoritmo depende de tres conceptos principales:
• Un camino de aumento, es una trayectoria desde el nodo fuente s al nodo sumidero t que puede conducir más flujo.
• La capacidad residual es lacapacidad adicional de flujo que un arco puede llevar cf (u,v) = c(u,v) - f(u,v)
• Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a lacapacidad del corte mínimo que separa a la fuente del destino.
El algoritmo es iterativo, se comienza con f(u,v)=0 para cada par de nodos y en cada iteración se incrementa el valor del flujo...