ALGORITMO DE FLUJO MAXIMO
Páginas: 6 (1370 palabras)
Publicado: 29 de noviembre de 2013
ALGORITMO DE FLUJO
MAXIMO
//JUAN FRANCISCO JAVIER MARTINEZ SANDOVAL//
Un poco de historia
Delbert Ray Fulkerson (*14 de agosto de 1924 - †10 de enero de 1976) fue
un matemático estadounidense que desarrolló como co-autor, y junto
con Lester Randolph Ford, Jr., el Algoritm de Ford-Fulkerson, uno de
los algoritmos más utilizados para computar el flujo máximo en una red de
flujo.Fulkerson recibió su Ph.D. en la Universidad de Wisconsin-Madison en
1951. En 1956, su importante artículo científico fue publicado. Desde
1979, la Sociedad de Programación Matemática (MPS) y la American
Mathematical Society (AMS) otorgan cada tres años el Premio Fulkerson,
para aquellos matemáticos que hayan creado artículos importantes en el
área de la matemática discreta.
APLICACIONES DEFLUJO MAXIMO
Extra……
Pasos para determinar algoritmo de flujo
máximo.
1. Identificar los nodos origen y destino.
2. Identificar la capacidad mas alta que sale del nodo origen.
3. Identificar el nodo intermediario con [αf, i]
4. Repetir como si el nodo intermediario fuera el nodo origen.
Formulario.
C = capacidad
i , j = índices de los nodos
K = flujo mínimo del caminoseleccionado
Cij,ji = (Ci-k, Cj+k)
FM=Σk
8
9
10
24
0
20
4
5
0
10
0
30
1
5
0
20
30
0
2
10
0
0
40
3
20
0
20
4
5
0
10
0
30
1
5
0
20
30
0
2
10
0
0
40
3
20
0
20
4
5
0
10
0
30
1
5
0
20
30
0
2
10
0
0
40
3
20
0
K min = [ⱷ, 30, 20 ] = 20
20
4C 13, 31 = (30-20, 0+20)
C 13, 31= (10, 20)
5
10
0
30
1
[ⱷ, - ]
C 35, 53 = (20-20, 0+20)
C 35, 53=(0, 20)
0
5
[20, 3 ]
0
20
30
0
0
2
0
40
10
3
20
[30, 1 ]
FORMULAS
0
K min = [ⱷ, 30, 20 ] = 20
20
4
C 13, 31 = (30-20, 0+20)
C 13, 31= (10, 20)
5
10
0
10
1
[ⱷ, - ]
C 35, 53 = (20-20, 0+20)
C 35, 53=(0, 20)
0
520
20
20
30
0
2
0
40
3
10
0
FORMULAS
K min = (ⱷ, 20, 40, 10, 20) = 10
[10, 3 ]
4
0
20
C 12, 21 = (20-10, 0+10)
C 12,21 = (10, 10)
5
0
10
0
10
1
[ⱷ, - ]
C 23,32 = (40-10, 0+10)
C 23,32 = (30, 10)
5
[20, 4]
20
20
20
30
0
2
[20, 1 ]
0
40
C 34,43 = (10-10, 5+10)
C 34,43 = (0 , 15)
C 45,54 = (20-10, 0+10)
C 45,54 =(10,10)
10
3
0
[40, 2 ]
FORMULAS
K min = (ⱷ, 20, 40, 10, 20) = 10
0
10
4
C 12, 21 = (20-10, 0+10)
C 12,21 = (10, 10)
15
10
10
1
[ⱷ, - ]
C 23,32 = (40-10, 0+10)
C 23,32 = (30, 10)
0
10
C 34,43 = (10-10, 5+10)
C 34,43 = (0 , 15)
5
20
10
20
30
10
2
10
30
3
C 45,54 = (20-10, 0+10)
C 45,54 =(10, 10)
0
0
FORMULAS
K min =(ⱷ, 20, 40, 10, 20) = 10
0
10
4
C 12, 21 = (20-10, 0+10)
C 12,21 = (10, 10)
15
10
10
1
[ⱷ, - ]
C 23,32 = (40-10, 0+10)
C 23,32 = (30, 10)
0
10
C 34,43 = (10-10, 5+10)
C 34,43 = (0 , 15)
5
20
10
20
30
10
2
10
30
3
C 45,54 = (20-10, 0+10)
C 45,54 =(10, 10)
0
0
FORMULAS
0
10
4
15
10
10
1
[ⱷ, - ]
0
10
5
20
1020
30
10
2
10
30
3
0
0
FORMULAS
K min = (ⱷ, 10, 30) = 10
0
10
4
C 12,21 = (10-10, 10+10)
C 12,21 = (0, 20)
15
10
10
1
[ⱷ, - ]
C 25,52 = (30-10, 0+10)
C 25,52 = (20, 10)
0
10
5
[30, 2 ]
20
10
20
30
10
2
[10, 1 ]
10
30
3
0
0
FORMULAS
K min = (ⱷ, 10, 30) = 10
0
10
4
C 12,21 = (10-10, 10+10)
C 12,21 = (0,20)
15
10
10
1
C 25,52 = (30-10, 0+10)
C 25,52 = (20, 10)
10
10
5
20
0
20
20
20
2
10
30
3
0
0
FORMULAS
0
10
4
15
10
10
1
[ⱷ, -]
10
10
5
ⱷ
20
0
20
20
20
2
10
30
3
0
0
FORMULAS
0
10
4
15
10
10
1
[ⱷ, -]
10
10
5
[20, 2]
ⱷ
20
0
20
20
20
2
[10, 3]
10...
MAXIMO
//JUAN FRANCISCO JAVIER MARTINEZ SANDOVAL//
Un poco de historia
Delbert Ray Fulkerson (*14 de agosto de 1924 - †10 de enero de 1976) fue
un matemático estadounidense que desarrolló como co-autor, y junto
con Lester Randolph Ford, Jr., el Algoritm de Ford-Fulkerson, uno de
los algoritmos más utilizados para computar el flujo máximo en una red de
flujo.Fulkerson recibió su Ph.D. en la Universidad de Wisconsin-Madison en
1951. En 1956, su importante artículo científico fue publicado. Desde
1979, la Sociedad de Programación Matemática (MPS) y la American
Mathematical Society (AMS) otorgan cada tres años el Premio Fulkerson,
para aquellos matemáticos que hayan creado artículos importantes en el
área de la matemática discreta.
APLICACIONES DEFLUJO MAXIMO
Extra……
Pasos para determinar algoritmo de flujo
máximo.
1. Identificar los nodos origen y destino.
2. Identificar la capacidad mas alta que sale del nodo origen.
3. Identificar el nodo intermediario con [αf, i]
4. Repetir como si el nodo intermediario fuera el nodo origen.
Formulario.
C = capacidad
i , j = índices de los nodos
K = flujo mínimo del caminoseleccionado
Cij,ji = (Ci-k, Cj+k)
FM=Σk
8
9
10
24
0
20
4
5
0
10
0
30
1
5
0
20
30
0
2
10
0
0
40
3
20
0
20
4
5
0
10
0
30
1
5
0
20
30
0
2
10
0
0
40
3
20
0
20
4
5
0
10
0
30
1
5
0
20
30
0
2
10
0
0
40
3
20
0
K min = [ⱷ, 30, 20 ] = 20
20
4C 13, 31 = (30-20, 0+20)
C 13, 31= (10, 20)
5
10
0
30
1
[ⱷ, - ]
C 35, 53 = (20-20, 0+20)
C 35, 53=(0, 20)
0
5
[20, 3 ]
0
20
30
0
0
2
0
40
10
3
20
[30, 1 ]
FORMULAS
0
K min = [ⱷ, 30, 20 ] = 20
20
4
C 13, 31 = (30-20, 0+20)
C 13, 31= (10, 20)
5
10
0
10
1
[ⱷ, - ]
C 35, 53 = (20-20, 0+20)
C 35, 53=(0, 20)
0
520
20
20
30
0
2
0
40
3
10
0
FORMULAS
K min = (ⱷ, 20, 40, 10, 20) = 10
[10, 3 ]
4
0
20
C 12, 21 = (20-10, 0+10)
C 12,21 = (10, 10)
5
0
10
0
10
1
[ⱷ, - ]
C 23,32 = (40-10, 0+10)
C 23,32 = (30, 10)
5
[20, 4]
20
20
20
30
0
2
[20, 1 ]
0
40
C 34,43 = (10-10, 5+10)
C 34,43 = (0 , 15)
C 45,54 = (20-10, 0+10)
C 45,54 =(10,10)
10
3
0
[40, 2 ]
FORMULAS
K min = (ⱷ, 20, 40, 10, 20) = 10
0
10
4
C 12, 21 = (20-10, 0+10)
C 12,21 = (10, 10)
15
10
10
1
[ⱷ, - ]
C 23,32 = (40-10, 0+10)
C 23,32 = (30, 10)
0
10
C 34,43 = (10-10, 5+10)
C 34,43 = (0 , 15)
5
20
10
20
30
10
2
10
30
3
C 45,54 = (20-10, 0+10)
C 45,54 =(10, 10)
0
0
FORMULAS
K min =(ⱷ, 20, 40, 10, 20) = 10
0
10
4
C 12, 21 = (20-10, 0+10)
C 12,21 = (10, 10)
15
10
10
1
[ⱷ, - ]
C 23,32 = (40-10, 0+10)
C 23,32 = (30, 10)
0
10
C 34,43 = (10-10, 5+10)
C 34,43 = (0 , 15)
5
20
10
20
30
10
2
10
30
3
C 45,54 = (20-10, 0+10)
C 45,54 =(10, 10)
0
0
FORMULAS
0
10
4
15
10
10
1
[ⱷ, - ]
0
10
5
20
1020
30
10
2
10
30
3
0
0
FORMULAS
K min = (ⱷ, 10, 30) = 10
0
10
4
C 12,21 = (10-10, 10+10)
C 12,21 = (0, 20)
15
10
10
1
[ⱷ, - ]
C 25,52 = (30-10, 0+10)
C 25,52 = (20, 10)
0
10
5
[30, 2 ]
20
10
20
30
10
2
[10, 1 ]
10
30
3
0
0
FORMULAS
K min = (ⱷ, 10, 30) = 10
0
10
4
C 12,21 = (10-10, 10+10)
C 12,21 = (0,20)
15
10
10
1
C 25,52 = (30-10, 0+10)
C 25,52 = (20, 10)
10
10
5
20
0
20
20
20
2
10
30
3
0
0
FORMULAS
0
10
4
15
10
10
1
[ⱷ, -]
10
10
5
ⱷ
20
0
20
20
20
2
10
30
3
0
0
FORMULAS
0
10
4
15
10
10
1
[ⱷ, -]
10
10
5
[20, 2]
ⱷ
20
0
20
20
20
2
[10, 3]
10...
Leer documento completo
Regístrate para leer el documento completo.