martes, 18 de mayo de 2010
El artículo de Ford y de Fulkerson (1956) con el problema de flujo máximo estableció el famoso teorema del flujo máximo - mínimo corte.
Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la menor capacidad es un corte mínimo proporciona el flujo máximo en la red.
Propiedad: v (f) =f(S, S’)-f(S', S).
El corte con la capacidad mas pequeña se denomina corte mínimo.
Cualquier nodo compatible desde el nodo fuente al nodo destino no puede exceder la capacidad de ningún corte. Por lo tanto, el flujo máximo a través de la red esta limitado por la capacidad del corte mínimo.
Para cualquier red del flujo máximo desde el nodo fuente al nodo destino es igual a la capacidad del corte destino.
A partir de este teorema el problema de encontrar el flujo máximo en una red se traduce en encontrar las capacidades de todos los cortes y elegir la minima capacidad. Por otra parte dado el valor máximo de flujo no especifica como este flujo es distribuido a tarves de los cortes que separan el nodo fuente del destino 2n-2.
Ejemplo:
En un grafo dirigido un conjunto de flechas S tal que todo camino dirigido de s a t contiene una flecha de S, decimos que S separa a s de t.
Un corte separa a s de t y un conjunto de flechas que separa a s de t es un corte.
En un grafo dirigido el número mínimo de flechas que separa a s de t es igual al máximo número de caminos dirigidos disjuntos de flechas que unen s con t.
NOTA: que si dos caminos dirigidos no tienen flechas comunes pueden tener vértices comunes. En cambio si dos caminos no tienen vértices comunes no tienen tampoco flechas comunes.
Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de regadíos, etc.
Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.
Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la menor capacidad es un corte mínimo proporciona el flujo máximo en la red.
Propiedad: v (f) =f(S, S’)-f(S', S).
El corte con la capacidad mas pequeña se denomina corte mínimo.
Cualquier nodo compatible desde el nodo fuente al nodo destino no puede exceder la capacidad de ningún corte. Por lo tanto, el flujo máximo a través de la red esta limitado por la capacidad del corte mínimo.
Para cualquier red del flujo máximo desde el nodo fuente al nodo destino es igual a la capacidad del corte destino.
A partir de este teorema el problema de encontrar el flujo máximo en una red se traduce en encontrar las capacidades de todos los cortes y elegir la minima capacidad. Por otra parte dado el valor máximo de flujo no especifica como este flujo es distribuido a tarves de los cortes que separan el nodo fuente del destino 2n-2.
Ejemplo:
En un grafo dirigido un conjunto de flechas S tal que todo camino dirigido de s a t contiene una flecha de S, decimos que S separa a s de t.
Un corte separa a s de t y un conjunto de flechas que separa a s de t es un corte.
En un grafo dirigido el número mínimo de flechas que separa a s de t es igual al máximo número de caminos dirigidos disjuntos de flechas que unen s con t.
NOTA: que si dos caminos dirigidos no tienen flechas comunes pueden tener vértices comunes. En cambio si dos caminos no tienen vértices comunes no tienen tampoco flechas comunes.
Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de regadíos, etc.
Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.
domingo, 16 de mayo de 2010
Proyecto #5 Problemas de Corte Minimo
Definición de corte minimo
En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedan dos partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra.
Definición de capacidad de un corte
Se llama capacidad de un corte a la suma:
S Capacidad (v,w) ; v Є V1 , w ЄV2
V1 es la parte que contiene a la fuente
V2 es la parte que contiene al sumidero
Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de F; es decir:
Si ЄP S JЄP Cij ³ S i F ai
La notación Si : Significa la suma sobre todos los vértices i
Demostración: observe Sj ЄP S iЄP Cji = Sj ЄP S iЄP F ij
Pues cada lado de la ecuación es simplemente la suma de Fij sobre todas las de i, j Є P
Ahora
S i F ai= Sj ЄP Sj Fji -Sj ЄP Sj
=Sj ЄP SiЄP Fji +Sj ЄP SiЄP Fji- =Sj ЄP SiЄP Fji
=Sj ЄP SiЄP Fji -Sj ЄP SiЄP Fji- £Sj ЄP SiЄP Fji£ Sj ЄP SiЄP Cji
El corte minimal nos da la minima capacidad del corte efectuado en el grafo.
Para el cálculo de la capacidad del corte minimal no se tienen en cuenta las capacidades de las aristas del corte cuya dirección sea contraria al sentido de flujo.
TEOREMA DEL FLUJO MÁXIMO Y EL CORTE MÍNIMO
Sea F un flujo en G y sea (P, P) un corte en G si la igualdad se cumple entonces el flujo es máximo y el corte es mínimo si y solo si:
1) FI J = CI J para i ЄP, J Є P
2) Fij =0 para i Є P, J Є P
El valor del flujo maximal de una red es igual a la capacidad del corte minimal que se puede aplicar a la red.
Se puede obtener, por tanto el corte minimal de una red, conociendo el flujo maximal de la red obtenido mediante la aplicación del algoritmo anteriormente definido.
En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedan dos partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra.
Definición de capacidad de un corte
Se llama capacidad de un corte a la suma:
S Capacidad (v,w) ; v Є V1 , w ЄV2
V1 es la parte que contiene a la fuente
V2 es la parte que contiene al sumidero
Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de F; es decir:
Si ЄP S JЄP Cij ³ S i F ai
La notación Si : Significa la suma sobre todos los vértices i
Demostración: observe Sj ЄP S iЄP Cji = Sj ЄP S iЄP F ij
Pues cada lado de la ecuación es simplemente la suma de Fij sobre todas las de i, j Є P
Ahora
S i F ai= Sj ЄP Sj Fji -Sj ЄP Sj
=Sj ЄP SiЄP Fji +Sj ЄP SiЄP Fji- =Sj ЄP SiЄP Fji
=Sj ЄP SiЄP Fji -Sj ЄP SiЄP Fji- £Sj ЄP SiЄP Fji£ Sj ЄP SiЄP Cji
El corte minimal nos da la minima capacidad del corte efectuado en el grafo.
Para el cálculo de la capacidad del corte minimal no se tienen en cuenta las capacidades de las aristas del corte cuya dirección sea contraria al sentido de flujo.
TEOREMA DEL FLUJO MÁXIMO Y EL CORTE MÍNIMO
Sea F un flujo en G y sea (P, P) un corte en G si la igualdad se cumple entonces el flujo es máximo y el corte es mínimo si y solo si:
1) FI J = CI J para i ЄP, J Є P
2) Fij =0 para i Є P, J Є P
El valor del flujo maximal de una red es igual a la capacidad del corte minimal que se puede aplicar a la red.
Se puede obtener, por tanto el corte minimal de una red, conociendo el flujo maximal de la red obtenido mediante la aplicación del algoritmo anteriormente definido.
Suscribirse a:
Entradas (Atom)
