Matematicas Discretas

Redes.(teorema de flujo máximo, teorema de flujo mínimo, pareos y redes de Petri)

Definición: Una Red de Transporte es una gráfica dirigida, simple, con pesos y que debe cumplir lassiguientes:

• Poseer una fuente 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 jllamado capacidad de “ij” es un numero 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 tienearistas 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 numero no negativo.Flujo maximo


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 estadirigida 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 el flujoen 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 aristasorientadas 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 flujoen ", 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...