RED DE TRANSPORTE
Definición:
Una Red de Transporte es una grafica dirigida, simple, con pesos y que debe cumplir las siguientes:
· 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 j llamado capacidad de “ij” es un numero no negativo.
Este es un ejemplo de una red que parte de un punto a que es un
Muelle y llega a un punto z que es una refinería.
Considerando la siguiente gráfica dirigida (red de transporte), que representa una tubería de petróleo. El petróleo se descarga en el muelle a y se bombea por toda la red de la refinería z . Los vértices b,c,d y e representan estaciones de bombeo intermedias. Las aristas dirigidas representan subtuberías del sistema y muestran la dirección en que puede fluir el petróleo. Las etiquetas de las aristas indican las capacidades de las subtuberías. El problema es encontrar la manera de maximizar el flujo del muelle a la refinería y calcular el valor de este flujo máximo.
Una red de transporte es una grafica 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 numero no negativo.
Si observamos la gráfica, el origen es el vértice a y el destino es el vértices z. La capacidad de la arista (a, b), C_{a, b} es 3 y la capacidad de la arista (b, c), C_{b, c} es 2. Un flujo en una red asigna un flujo a cada arista dirigida que no excede la capacidad de esa arista. Más aun, si se supone que el flujo que entra a un vértice v, que no es el origen y el destino, es igual al flujo que sale de v.
Ejemplo de red de transporte
Tomado con referencia la gráfica:
Sea G una red de transporte. Sea C_{ij} la capacidad de la arista dirigida (i, j) . Un flujo F en G asigna a cada arista dirigida (i, j) un numero no negativo F_{ij} tal que:
a. F_{ij} ≤ C_{ij}
b. Para cada vértice j, que no es la fuente ni el destino.
Conservación de flujo
- F_{ij} recibe el nombre de flujo en la arista (i, j). Para cualquier vértice j,
- Se llama flujo que entra a j y
- Se llama flujo que sale de j.
Conservación de flujo significa para el ejemplo, que el petróleo no se usa ni se suministra en las estaciones de bombeo b, c, d y e.
Ahora, vamos a definir un flujo para la red del ejemplo asignando los valores:
F_{ab} = 2, F_{bc} = 2, F_{cz} = 3; F_{ad} = 3, F_{dc} = 1, F_{de} = 2, F_{ez} = 2
La gráfica quedaría,
Definición:
Sea “G” una red y sea “Cij” la capacidad de la arista dirigida (ij) se dice que un flujo F en G asigna a cada arista dirigida (ij) un numero no negativo Fij tal que debe cumplir:
· Fij ≤ Cij
· Para todos los vértices que no sea fuente ni sumidero se cumple: ec 8.1.1 (esta es la ecuación de conservación de flujo)
Teorema 1:
Dado un flujo F en una red el flujo de salida de la fuente es igual al flujo de entrada del sumidero.
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 flujo 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.
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 el flujo 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”
a) 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.
b) 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.
c) Es análogo en el caso b
d) Disminuimos el flujo en ambas aristas en ∆. En cada caso las asignaciones resultantes de las aristas dan como resultado un flujo.
Para realizar estas alteraciones debemos tener un flujo menor que la capacidad en una arista orientada en forma propia y un flujo distinto de cero en una arista orientada en forma impropia.
Teorema 2:
Sea P un camino de “a” a ”z” en una red G tal que:
a) Para cada arista (i,j) de P, orientada en forma propia.
Fij <Cij
b) Para cada arista (i,j) de P, orientada en forma impropia
0 <Fij
Se define
F’ij =
Si no existieran caminos que concuerden con el teorema 2, el flujo es máximo, entonces se considera el algoritmo:
1- Iniciar con un flujo
2- Buscar un camino que satisfaga con las condiciones del teorema 2
3- Si no existe el camino el flujo es máximo.
4- Se incrementa el flujo en ∆, y se regresa a línea 2.
A dicho algoritmo se le llama Algoritmo etiquetado.
Teorema de flujo máximo y corte mínimo
Tenemos una red G y tiene un flujo F al concluir nuestro algoritmo esto significa que algunos vértices están etiquetados y otros no. Sea P el conjunto de vértices Etiquetados y (Ā no complementados) entonces la fuente a no esta en P y el sumidero z esta Ā. El conjunto s de aristas (v,w) con v que pertenece a P y w que pertenece a Ā, es un corte y la suma de las capacidades de las aristas s es la capacidad de cortes.
Para el caso G es una red con una fuente a y un sumidero z luego la capacidad de las aristas i,j es Cij
Un corte (P, Ā) donde el complemento de P es Ā en G consta de un conjunto P de vértices y de complementos a Ā, donde a pertenece a P y z pertenece a Ā.
Teorema 3
Sea F un flujo en G y teniendo (P, Ā) un corte en G entonces la capacidad de este es mayor o igual que el valor de F; es decir
Teorema 4
Siendo F un flujo en G sea (P, Ā) Un corte en G, si la igualdad se cumple en Un corte (P, Ā) donde el complemento de P es Ā en G consta de un conjunto P de vértices y de complementos a Ā, donde a pertenece a P y z pertenece a Ā. Entonces se dice que el flujo es máximo y el corte es mínimo. La igualdad se cumple sí y solo sí:
a) Fij =Cij Para i que pertenece a P, j pertenece a Ā.
b) Fij = 0 Para i que pertenece a Ā, j pertenece a P.
Teorema 5
Cuando se concluye un algoritmo se produce un flujo máximo, si P (respectivamente, Ā) es el conjunto de vértices etiquetados (respectivamente, no etiquetados) al concluir el algoritmo el corte (P, Ā) es mínimo.
Aqui un video de: