Problema de flujo
Páginas: 3 (733 palabras)
Publicado: 20 de junio de 2011
Problema de flujo máximo
Sea un grafo dirigido. A cada arista se le asocia un número real positivo, llamado capacidad y denotado por , donde , correspondiente a la máxima cantidad de fluido que escapaz de transportar. Además se distinguen un nodo origen y un nodo destino , donde es una fuente que alcanza a todos los otros nodos y es un sumidero alcanzado por éstos. La figura 1 muestra un grafoque modela una red con capacidades, con fuente y sumidero . Una consideración importante es que, cuando se tienen flujos en ambos sentidos, no necesariamente deben ser iguales. FIGURA 1: Ejemplo dered con capacidades.
La pregunta a responder es: ¿cuál es el flujo máximo que puede entrar por la fuente y salir por el sumidero en una unidad de tiempo? Para responder esta pregunta, se debe teneren consideración que, para cada nodo intermedio (cada nodo que no es la fuente ni el sumidero) se debe cumplir que el flujo entrante sea igual al flujo saliente. El algoritmo para resolver esteproblema, propuesto por Ford y Fulkerson, resulta bastante sencillo y se basa en el sentido común, como se puede apreciar en el algoritmo 1. ALGORITMO 1: Ford-Fulkerson. 1. Hacer el flujo máximo . 2.Encontrar un camino desde la fuente hasta el sumidero que tenga una capacidad de flujo mayor que 0. 3. Encontrar la arista del camino con la menor capacidad e incrementar F en dicha capacidad. 4. Crear unared residual en que, para cada arista del camino, se descuente la capacidad encontrada en el paso anterior. 5. Repetir el algoritmo en la red residual.
Dra. Mónica Villanueva I. (USACH) - Mag.Jacqueline Köhler C. (UNAB)
EJEMPLO: Determinación del flujo máximo para una red. Considere la red de la figura 1. Inicialmente, se tiene ser 1-2-5-7, donde: , capacidad es . En consecuencia, ahora setiene FIGURA 2: Red residual tras estudiar el camino 1-2-5-7. . Un primer camino desde hacia t puede y . Así, la arista de menor . La red residual se muestra en la figura 2.
De manera similar, en...
Sea un grafo dirigido. A cada arista se le asocia un número real positivo, llamado capacidad y denotado por , donde , correspondiente a la máxima cantidad de fluido que escapaz de transportar. Además se distinguen un nodo origen y un nodo destino , donde es una fuente que alcanza a todos los otros nodos y es un sumidero alcanzado por éstos. La figura 1 muestra un grafoque modela una red con capacidades, con fuente y sumidero . Una consideración importante es que, cuando se tienen flujos en ambos sentidos, no necesariamente deben ser iguales. FIGURA 1: Ejemplo dered con capacidades.
La pregunta a responder es: ¿cuál es el flujo máximo que puede entrar por la fuente y salir por el sumidero en una unidad de tiempo? Para responder esta pregunta, se debe teneren consideración que, para cada nodo intermedio (cada nodo que no es la fuente ni el sumidero) se debe cumplir que el flujo entrante sea igual al flujo saliente. El algoritmo para resolver esteproblema, propuesto por Ford y Fulkerson, resulta bastante sencillo y se basa en el sentido común, como se puede apreciar en el algoritmo 1. ALGORITMO 1: Ford-Fulkerson. 1. Hacer el flujo máximo . 2.Encontrar un camino desde la fuente hasta el sumidero que tenga una capacidad de flujo mayor que 0. 3. Encontrar la arista del camino con la menor capacidad e incrementar F en dicha capacidad. 4. Crear unared residual en que, para cada arista del camino, se descuente la capacidad encontrada en el paso anterior. 5. Repetir el algoritmo en la red residual.
Dra. Mónica Villanueva I. (USACH) - Mag.Jacqueline Köhler C. (UNAB)
EJEMPLO: Determinación del flujo máximo para una red. Considere la red de la figura 1. Inicialmente, se tiene ser 1-2-5-7, donde: , capacidad es . En consecuencia, ahora setiene FIGURA 2: Red residual tras estudiar el camino 1-2-5-7. . Un primer camino desde hacia t puede y . Así, la arista de menor . La red residual se muestra en la figura 2.
De manera similar, en...
Leer documento completo
Regístrate para leer el documento completo.