Algoritmos sobre camino

TAREA: ALGORITMOS SOBRE CAMINOS Y CONEXIDAD

Una empresa de entrega de encomiendas desea establecer una ruta adecuada para la distribución de los envíos que le encargan los clientes. Los vehículos salen del distrito A llevando los envíos y retornan al terminar la entrega en los distritos B, C, D, E. La información de la siguiente matriz contiene los costos de transporte por llevar una encomienda del distrito i al distrito j.

1. Diseñar el grafo sagital.

[pic 1][pic 2][pic 3]

[pic 4]

[pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11]

[pic 12][pic 13][pic 14]

[pic 15][pic 16][pic 17]

[pic 18]

[pic 19]

1. Hallar el espectro positivo del nodo D.

[pic 20][pic 21][pic 22][pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39]

1. Hallar el espectro negativo del nodo D.

          (D) = {A, C, E}[pic 40]

       (D)=  ((D)) =  {A, C, E} = {A}U{{C} U{E}[pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47]

                                             = {B, E, D} U {B, E, D} U {D}[pic 48]

         (D)= ({A, B, D} ={A}U{B} U{D}[pic 49][pic 50][pic 51][pic 52][pic 53]

                                               {A, B, D} U {A, C, D} U {C, E, A} = {A, B, C, D, E}

1. Determinar aplicando el algoritmo de Roy si el grafo es o no f-conexo. Si no lo es, indicar sus componentes f-conexas.

[pic 54]

Paso 1[pic 55]

[pic 56][pic 57][pic 58]

[pic 59][pic 60]

[pic 61][pic 62][pic 63][pic 64][pic 65][pic 66][pic 67]

[pic 68]

[pic 69][pic 70][pic 71][pic 72]

[pic 73][pic 74][pic 75]

[pic 76]

[pic 77]

[pic 78]

1. Determinar mediante el algoritmo de Malgrange si el grafo es o no f-conexo y comparar con los resultados obtenidos en ©.

[pic 79][pic 80][pic 81]

[pic 82]

[pic 83][pic 84][pic 85][pic 86][pic 87][pic 88][pic 89]

[pic 90][pic 91][pic 92]

[pic 93][pic 94][pic 95]

[pic 96]

[pic 97]

 Elijo a

       (A)= {A, B, C, D, E}[pic 98]

      (A)= {A, B, C, D, E}[pic 99]

     (A)      (A) = {A, B, C, D, E}   Componente f- conexa [pic 100][pic 101][pic 102]

Elijo d

       (D)= {A, B, C, D, E}[pic 103]

      (D)= {A, B, C, D, E}[pic 104]

      (A)      (A) = {A, B, C, D, E}[pic 105][pic 106][pic 107]

     Solo tiene un componente f-conexo que es {A, B, C, D, E}

1. Construir la matriz latina.

1. Hallar mediante multiplicación latina los caminos y circuitos Hamiltonianos.

[pic 108]

                                                                                        *                                                                                                                                                                                            

...