Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 78 vistas

    Ejercicios - Guzman

    Cargado por

    Carlos Alberto Junior Guzman Narvaez
    Este documento presenta 4 problemas que involucran algoritmos para redes. El Problema 1 y 2 usan el algoritmo de Dijkstra para encontrar las rutas óptimas entre nodos. El Problema 3 y 4 usan el algoritmo de Ford-Fulkerson para determinar el flujo máximo en una red aplicando iteraciones que suman y restan capacidades de los arcos.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Ejercicios - Guzman

    Cargado por

    Carlos Alberto Junior Guzman Narvaez
    78 vistas13 páginas
    Este documento presenta 4 problemas que involucran algoritmos para redes. El Problema 1 y 2 usan el algoritmo de Dijkstra para encontrar las rutas óptimas entre nodos. El Problema 3 y 4 usan el algoritmo de Ford-Fulkerson para determinar el flujo máximo en una red aplicando iteraciones que suman y restan capacidades de los arcos.

    Descripción original:

    Ejercicio

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta 4 problemas que involucran algoritmos para redes. El Problema 1 y 2 usan el algoritmo de Dijkstra para encontrar las rutas óptimas entre nodos. El Problema 3 y 4 usan el algoritmo de Ford-Fulkerson para determinar el flujo máximo en una red aplicando iteraciones que suman y restan capacidades de los arcos.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    78 vistas13 páginas

    Ejercicios - Guzman

    Cargado por

    Carlos Alberto Junior Guzman Narvaez
    Este documento presenta 4 problemas que involucran algoritmos para redes. El Problema 1 y 2 usan el algoritmo de Dijkstra para encontrar las rutas óptimas entre nodos. El Problema 3 y 4 usan el algoritmo de Ford-Fulkerson para determinar el flujo máximo en una red aplicando iteraciones que suman y restan capacidades de los arcos.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 13

    Ejercicios sobre redes

    Problema 1: Utilice el algoritmo de Dijkstra para determinar la solución óptima de la


    siguiente RED, Compruebe con el programa TORA la solución.

    A partir del nodo 1 se escoge el arco de menor distancia conectado y se etiqueta con corchetes
    señalando la distancia y el nodo del cual precede dicha dimensión. El color negro señala la
    distancia y el marron el nodo del cual precede.Ademas se pinta con color verde los nodos para
    indicar que ruta se
    La ruta mas corta del nodo 1 al nodo 8 es igual a :8

    Existen otras ruta alternativas que tienen la misma distancia como las siguientes:
    Problema 2:
    Utilice el algoritmo de Dijkstra para determinar las mejores rutas que deben seguir la flota
    de repartición de una Mini Market los datos se encuentren en la siguiente RED. Compruebe
    con el programa TORA la solución.

    A partir del nodo 1 se escogen las menores distancias y se etiquetan los nodos indicando con
    negro las distancias que lo conectan con un nodo anterior y con marrón dichas distancia.
    Problema 3:
    Utilice el algoritmo de Ford-Fulkerson determine el flujo máximo para la siguiente RED.
    Compruebe con el programa TORA la solución.

    Se escoge el arco de mayor capacidad, se pinta de amarillo, para hallar el máximo flujo del
    nodo 1 al nodo 5

    Se seleccionan las capacidades de los arcos seleccionados y se escoge la menor que va


    ser representada por K.

    K =Min (∞;14;10) =10

    Este valor, K, se va a sumar a las capacidades de los nodos receptores en


    los arcos y restar a las capacidades de los nodos distribuidores de flujo
    mediante la siguiente formula:
    C ij ji = (Ci –K; Cj+k)
    Donde C representa la capacidad, i,J los índices de los nodos y K es el menor valor de
    flujo que se traspasa del nodo origen al destino.
    Aplicando estas ideas se obtienen las siguientes operaciones:
    C 13 31 = (14-10;0+10) =4;10
    C 35 53 = (10-10;0+10) = 0;10
    2 iteración:

    K2 =Min (∞;8;7;5) =5

    C ij ji = (Ci –K; Cj+k)


    C 12 21 = (8-5;0+5) =3;5
    C 24 42 = (7-5;6+5) = 2;11
    C 45 54 = (5-5;0+5) =0;5
    3 iteración:

    K3 =Min (∞;4;10;6) =4

    C ij ji = (Ci –K; Cj+k)


    C 13 31 = (4-4;10+4) =0;14
    C 32 23 = (10-4;5+4) = 6;9
    C 25 52 = (6-4;0+4) =2;4
    4 Iteración:

    K4 =Min (∞;4) =4
    C ij ji = (Ci –K; Cj+k)
    C 15 51 = (4-4;0+4) =0;4
    5ta iteración:

    K5 =Min (∞;3;2) =2

    C ij ji = (Ci –K; Cj+k)


    C 12 21 = (3-2;5+2) =1;7
    C 25 52 = (2-2;4+2) =0;6
    6 iteración:
    El flujo máximo que puede ir por esta red de nodos es = a
    k1+k2+k3+k4+k5 = 10+5+4+4+2=25.

    Problema 4:
    Utilice el algoritmo de Ford-Fulkerson determine el flujo máximo para la siguiente
    RED. Compruebe con el programa TORA la solución

    1 iteración:

    K1 =Min (∞;6;4;4) =4

    C ij ji = (Ci –K; Cj+k)


    C 12 21 = (6-4;0+4) =2;4
    C 25 52 = (4-4;0+4) =0;4
    C 57 75 = (4-4;0+4) =0;4

    2 iteración:

    K2 =Min (∞;4;3;9) =3

    C ij ji = (Ci –K; Cj+k)


    C 13 31 = (4-3;0+3) =1;3
    C 36 63 = (3-3;0+3) =0;3
    C 67 76 = (9-3;0+3) =6;3
    3 iteración:
    K3 =Min (∞;1;3;4;6) =1

    C ij ji = (Ci –K; Cj+k)


    C 13 31 = (1-1;3+1) =0;4
    C 34 43 = (3-1;0+1) =2;1
    C 46 64 = (4-1;0+1) =3;1
    C 67 76 = (6-1;3+1) =5;4
    4 iteración:

    K4 =Min (∞;1;3;5;) =1

    C ij ji = (Ci –K; Cj+k)


    C 14 41 = (1-1;0+1) =0;1
    C 46 64 = (3-1;1+1) =4;2
    C 67 76 = (5-1;4+1) =4;5
    5 iteración:

    El flujo máximo que puede ir por esta red de nodos es = a k1+k2+k3+k4=4+3+1+1=9.

    Problema 4:
    Problema 2:

    También podría gustarte