Clase6MiniSem
Páginas: 12 (2827 palabras)
Publicado: 9 de mayo de 2015
Flujo máximo: Redes de flujo y
método de Ford-Fulkerson
Jose Aguilar
b
2
s
d
1
a
3
t
c
2
2
45
3
4
1
3
2
10
5
25
40
55
30
25
50
4
15
Flujo en Redes. Flujo máximo
20
3
Algoritmos de Flujos
Los algoritmos de flujos resuelven el problema de
encontrar el flujo máximo de una fuente a un sumidero
respetando una serie de restricciones.
•
Los flujos se miden como el flujoque sale de un nodo,
si así ocurriera el flujo se considera positivo, en caso
contrario tenemos un flujo negativo.
• La fuente tiene un flujo neto positivo, el sumidero tiene
un flujo neto negativo, y los nodos intermedios en los
caminos que van de la fuente al sumidero tienen un
flujo neto igual a cero.
propiedad de conservación del flujo
fi = fo (por nodo).
Equivalente a las leyes deconservación de la materia
en física y leyes de Kirchoff en electricidad.
Algoritmos de Flujos
Usos: modelado de flujo en tuberías, piezas a través de
líneas de ensamblado, corrientes en redes eléctricas,
información en redes de comunicación, etc.
Una red de flujo G=(N,A) es un grafo dirigido tal que cada arco
(u,v)A posee una capacidad c(u,v)0. Si (u,v)A, c(u,v)=0.
• Se distinguen 2 vértices, el fuente“s” y el destino “t”. Cada vértice
vN esta en algún s~>v~>t.
• El grafo es conexo |A||N|-1
peso de las aristas representa la capacidad máxima de
transportar un flujo.
Algoritmos de Flujos
• Problema: Maximizar la cantidad de flujo desde
un vértice fuente a otro sumidero, sin superar las
restricciones de capacidad.
– Método de Ford-Fulkerson para resolver el problema
de máximo flujo.
Problemadel flujo máximo: encontrar la rata máxima a la
cual el material puede ser transportado de una fuente (s) a
un destino (t), sin violar las restricciones de capacidad de la red.
Flujo Máximo
• Restricciones:
– La suma de las entradas de cada nodo interior debe ser igual a
la suma de sus salidas.
– Los valores de flujo en cada arista no pueden superar los
valores máximos.
b
5
G
s
2
d
3
41
3
a
t
2
J. Aguilar
c
4
6
Flujo Máximo
• Solución. G: grafo del problema. F: grafo resultante.
G
5
s
b
1
3
a
2
d
F
3
4
t
2
c
4
2
s
b
0
3
a
2
d
3
1
t
2
c
2
• El problema se puede resolver de forma eficiente.
• Posible algoritmo:
– Encontrar un camino cualquiera desde s hasta t.
– El máximo flujo que puede ir por ese camino es el mínimo coste de las
aristas quelo forman, m.
– Sumar m en el camino en F, y restarlo de G.
• Ojo: este algoritmo no garantiza solución óptima.
Redes de flujo
• Digrafo G=(V, E)
• Los pesos de las aristas representan capacidad (c(u,
v)> 0). Si no hay aristas la capacidad es cero.
• Vértices especiales:
fuente s, vértice sin aristas de entrada.
sumidero t, vértice sin aristas de salida.
• El grafo es conectado: Hay un caminoentre s y t por
algún vértice intermedio del grafo.
J. Aguilar
8
Redes de flujo
• Un flujo en G es una función real f : VxV que satisface
las siguientes propiedades:
– Restricción de capacidad: Para todo u, v V, f (u, v) < c (u, v)
– Antisimetría: Para todo u, v V, f (u, v) = f (v, u)
– Conservación de flujo: Para todo u V {s, t },
• Valor del flujo: | f | =
12 / 12
v2
v3
7/710
1/4
v1
s
=
11 / 16
v4
t
=0
El problema del flujo máximo
Se define como: dado G, s (fuente) y t (destino)
encontrar el flujo neto total máximo desde s hasta t
Flujo neto positivo entrando a un nodo v es
uN F(u,v)
y el que sale se define simétricamente.
J. Aguilar
10
Algoritmo de Ford-Fulkerson
Es un método iterativo que depende de tres ideas
importantes:
• Red residual
• Aumento decamino
• Cortes
Usa el teorema max-flow min-cut que caracteriza el flujo
máximo en términos de cortes de la red de flujo.
En cada iteración se va consiguiendo un valor de flujo que
aumenta el camino, es decir, podemos aumentar el flujo en un
camino de s a t. Este proceso se repite hasta que no haya más
posibilidad de aumentar.
J. Aguilar
11
Flujo residual
Es el flujo disponible en una...
método de Ford-Fulkerson
Jose Aguilar
b
2
s
d
1
a
3
t
c
2
2
45
3
4
1
3
2
10
5
25
40
55
30
25
50
4
15
Flujo en Redes. Flujo máximo
20
3
Algoritmos de Flujos
Los algoritmos de flujos resuelven el problema de
encontrar el flujo máximo de una fuente a un sumidero
respetando una serie de restricciones.
•
Los flujos se miden como el flujoque sale de un nodo,
si así ocurriera el flujo se considera positivo, en caso
contrario tenemos un flujo negativo.
• La fuente tiene un flujo neto positivo, el sumidero tiene
un flujo neto negativo, y los nodos intermedios en los
caminos que van de la fuente al sumidero tienen un
flujo neto igual a cero.
propiedad de conservación del flujo
fi = fo (por nodo).
Equivalente a las leyes deconservación de la materia
en física y leyes de Kirchoff en electricidad.
Algoritmos de Flujos
Usos: modelado de flujo en tuberías, piezas a través de
líneas de ensamblado, corrientes en redes eléctricas,
información en redes de comunicación, etc.
Una red de flujo G=(N,A) es un grafo dirigido tal que cada arco
(u,v)A posee una capacidad c(u,v)0. Si (u,v)A, c(u,v)=0.
• Se distinguen 2 vértices, el fuente“s” y el destino “t”. Cada vértice
vN esta en algún s~>v~>t.
• El grafo es conexo |A||N|-1
peso de las aristas representa la capacidad máxima de
transportar un flujo.
Algoritmos de Flujos
• Problema: Maximizar la cantidad de flujo desde
un vértice fuente a otro sumidero, sin superar las
restricciones de capacidad.
– Método de Ford-Fulkerson para resolver el problema
de máximo flujo.
Problemadel flujo máximo: encontrar la rata máxima a la
cual el material puede ser transportado de una fuente (s) a
un destino (t), sin violar las restricciones de capacidad de la red.
Flujo Máximo
• Restricciones:
– La suma de las entradas de cada nodo interior debe ser igual a
la suma de sus salidas.
– Los valores de flujo en cada arista no pueden superar los
valores máximos.
b
5
G
s
2
d
3
41
3
a
t
2
J. Aguilar
c
4
6
Flujo Máximo
• Solución. G: grafo del problema. F: grafo resultante.
G
5
s
b
1
3
a
2
d
F
3
4
t
2
c
4
2
s
b
0
3
a
2
d
3
1
t
2
c
2
• El problema se puede resolver de forma eficiente.
• Posible algoritmo:
– Encontrar un camino cualquiera desde s hasta t.
– El máximo flujo que puede ir por ese camino es el mínimo coste de las
aristas quelo forman, m.
– Sumar m en el camino en F, y restarlo de G.
• Ojo: este algoritmo no garantiza solución óptima.
Redes de flujo
• Digrafo G=(V, E)
• Los pesos de las aristas representan capacidad (c(u,
v)> 0). Si no hay aristas la capacidad es cero.
• Vértices especiales:
fuente s, vértice sin aristas de entrada.
sumidero t, vértice sin aristas de salida.
• El grafo es conectado: Hay un caminoentre s y t por
algún vértice intermedio del grafo.
J. Aguilar
8
Redes de flujo
• Un flujo en G es una función real f : VxV que satisface
las siguientes propiedades:
– Restricción de capacidad: Para todo u, v V, f (u, v) < c (u, v)
– Antisimetría: Para todo u, v V, f (u, v) = f (v, u)
– Conservación de flujo: Para todo u V {s, t },
• Valor del flujo: | f | =
12 / 12
v2
v3
7/710
1/4
v1
s
=
11 / 16
v4
t
=0
El problema del flujo máximo
Se define como: dado G, s (fuente) y t (destino)
encontrar el flujo neto total máximo desde s hasta t
Flujo neto positivo entrando a un nodo v es
uN F(u,v)
y el que sale se define simétricamente.
J. Aguilar
10
Algoritmo de Ford-Fulkerson
Es un método iterativo que depende de tres ideas
importantes:
• Red residual
• Aumento decamino
• Cortes
Usa el teorema max-flow min-cut que caracteriza el flujo
máximo en términos de cortes de la red de flujo.
En cada iteración se va consiguiendo un valor de flujo que
aumenta el camino, es decir, podemos aumentar el flujo en un
camino de s a t. Este proceso se repite hasta que no haya más
posibilidad de aumentar.
J. Aguilar
11
Flujo residual
Es el flujo disponible en una...
Leer documento completo
Regístrate para leer el documento completo.