Análisis y diseños de algoritmos

UNIVERSIDAD NACIONAL DEL ALTIPLANO

FACULTAD DE INGENIERÍA ESTADÍSTICA E INFORMÁTICA

ESCUELA PROFESIONAL DE INGENIERÍA ESTADÍSTICA E INFORMÁTICA

        [pic 1]

TRABAJO ENCARGADO N° IV

PLANTEAR 3 GRAFOS (1 DIRIGIDO Y 2 NO DIRIGIDOS), LUEGO HALLAR LA DISTANCIA DE UN NODO

PRESENTADO POR:

CRUZ CHOQUEHUANCA HECTOR ALAN

CURSO:

ANALISIS Y DISEÑOS DE ALGORITMOS

ENCARGADO:

HUATA PANCA PERCY

II - SEMESTRE 2022

PUNO, PERU

JUNIO - 2022

TRABAJO

PLANTEAR 3 GRAFOS (1 DIRIGIDO Y 2 NO DIRIGIDOS), LUEGO HALLAR LA DISTANCIA DE UN NODO

• GRAFO DIRGIDO [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]

[pic 20][pic 21]

[pic 22][pic 23]

Primer paso: partimos del nodo 2 cuyas salidas son al nodo 3,4 y 6 en cada una de ellas se coloca su notación [2,2](1),[6,2](1),[2,2](1).

[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]

[pic 40][pic 41][pic 42][pic 43][pic 44]

[pic 45][pic 46]

[pic 47][pic 48]

Segundo paso: partimos del nodo 3 ya que tiene la menor distancia de las otras que son 6 y 2 y la notación seria [3,3](2).

[pic 49]

[pic 50][pic 51][pic 52][pic 53]

[pic 54][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]

Tercer paso: continuamos con el nodo 4 eligiendo la menor distancia entre los 3 (3,6 y 2) de este modo tenemos 2 salidas al nodo 5 y 6 donde seria [6,4](2) y [5,4](2)  se tacha los que tienen mayor distancia

                                                      [3,3](2)

                                                    [6,4](2)[pic 75]

                   [pic 76][pic 77][pic 78][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]

[pic 98][pic 99]

[pic 100][pic 101]

[pic 102]

                                               [6,2](1)

                                                [5,4](2)

Cuarto paso: continuamos con el nodo 5 eligiendo la menor distancia (3 y 5) de esta manera tenemos una salida al nodo 1 donde colocamos la notación [4,5](3) ya que los nodos 3 y 4 ya fueron evaluados quedaría por evaluar el nodo 6.

                                                      [3,3](2)

                                                    [6,4](2)[pic 103]

                   [pic 104][pic 105][pic 106][pic 107]

[pic 108][pic 109][pic 110][pic 111][pic 112][pic 113]

[pic 114][pic 115][pic 116]

[pic 117][pic 118]

                                                                                            [4,5](3)[pic 119][pic 120][pic 121]

[pic 122][pic 123][pic 124][pic 125][pic 126]

[pic 127][pic 128]

[pic 129][pic 130]

[pic 131]

                                               [6,2](1)

                                                [5,4](2)

 Quinto paso: continuamos con el nodo 6 eligiendo la distancia 5 por que la distancia 3 ya fue evaluado tachamos las distancias largas y nos queda el [4,5](3)

                                                      [3,3](2)

                                                    [6,4](2)[pic 132]

                   [pic 133][pic 134][pic 135][pic 136]

[pic 137][pic 138][pic 139][pic 140][pic 141][pic 142]

...