Redes
Páginas: 3 (502 palabras)
Publicado: 7 de noviembre de 2012
Modelo del Flujo Máximo
Flujo Máximo
Flujo Máximo
Flujo Máximo
Flujo Máximo
Ejemplo
5
Paso 1
5
[20,3] Menor K1=20
+ +
-
[30,1]
Paso 1
5
10 20 20 0[30,1] [20,3]
K1=20
Paso 2
5
Paso 2
Menor K2=10 5
+
+
K2=10 + +
Paso 2
15
Paso 3
15
+
-
+ K3=10
Menor K3=10
Paso 3
15
Paso 4
15 10
-
+
+ ++ Menor K4=10 K4=10
Paso 4
15
Paso 5
15
K5=10
Paso 5
15
Ejercicio Propuesto
0
2 5
8
0 4
5 4
8
0 18
1 15 20 0 4 5 4 6 3 7 6 8
0 3
4 7
0 7
47 8 0
0 8
0
EL ÁRBOL DE EXPANSIÓN MÍNIMA
• Es un problema clásico de optimización combinatoria, formulado en 1926 por Boruvka quien lo planteó para resolver el problema de hallar la formamás económica de distribuir energía eléctrica en el sur de Moravia. La formulación de este problema ha sido útil para la realización de muchas investigaciones en varios campos como el transporte,electrónica, telecomunicaciones e investigación de operaciones. • El modelo contempla un conjunto de arcos que conectan todos los nodos de la red sin crear un solo ciclo o vuelta. El problema consiste endeterminar el árbol que minimiza la distancia de conexión total; se resuelve por el Algoritmo de Etiquetado. En cuanto a la introducción de datos y el proceso de solución es similar a los modelosanteriores de este módulo.
Algoritmo de árbol de expansión mínima
Un árbol es un grafo que tiene sus n nodos (vértices) conectados (conexo) con n-1 arcos (aristas), no existiendo ciclos (caminoscerrados)
Un árbol de expansión de costo mínimo es aquel en que todos los enlaces tienen longitudes (costos) mínimas
Algoritmo para el problema del árbol de expansión mínima.
Método Gráfico
1 2Nota:
Se selecciona un nodo cualquiera y se conecta al nodo más cercano a éste. Se identifica el nodo no conectado más cercano a un nodo conectado y se conectan estos dos nodos Empates se deciden...
Flujo Máximo
Flujo Máximo
Flujo Máximo
Flujo Máximo
Ejemplo
5
Paso 1
5
[20,3] Menor K1=20
+ +
-
[30,1]
Paso 1
5
10 20 20 0[30,1] [20,3]
K1=20
Paso 2
5
Paso 2
Menor K2=10 5
+
+
K2=10 + +
Paso 2
15
Paso 3
15
+
-
+ K3=10
Menor K3=10
Paso 3
15
Paso 4
15 10
-
+
+ ++ Menor K4=10 K4=10
Paso 4
15
Paso 5
15
K5=10
Paso 5
15
Ejercicio Propuesto
0
2 5
8
0 4
5 4
8
0 18
1 15 20 0 4 5 4 6 3 7 6 8
0 3
4 7
0 7
47 8 0
0 8
0
EL ÁRBOL DE EXPANSIÓN MÍNIMA
• Es un problema clásico de optimización combinatoria, formulado en 1926 por Boruvka quien lo planteó para resolver el problema de hallar la formamás económica de distribuir energía eléctrica en el sur de Moravia. La formulación de este problema ha sido útil para la realización de muchas investigaciones en varios campos como el transporte,electrónica, telecomunicaciones e investigación de operaciones. • El modelo contempla un conjunto de arcos que conectan todos los nodos de la red sin crear un solo ciclo o vuelta. El problema consiste endeterminar el árbol que minimiza la distancia de conexión total; se resuelve por el Algoritmo de Etiquetado. En cuanto a la introducción de datos y el proceso de solución es similar a los modelosanteriores de este módulo.
Algoritmo de árbol de expansión mínima
Un árbol es un grafo que tiene sus n nodos (vértices) conectados (conexo) con n-1 arcos (aristas), no existiendo ciclos (caminoscerrados)
Un árbol de expansión de costo mínimo es aquel en que todos los enlaces tienen longitudes (costos) mínimas
Algoritmo para el problema del árbol de expansión mínima.
Método Gráfico
1 2Nota:
Se selecciona un nodo cualquiera y se conecta al nodo más cercano a éste. Se identifica el nodo no conectado más cercano a un nodo conectado y se conectan estos dos nodos Empates se deciden...
Leer documento completo
Regístrate para leer el documento completo.