TALLER SEGUNDO CORTE

1. Para cada uno de los siguientes grafos determine las matrices de adyacencia e incidencia. Utilice la potencia de las matrices de adyacencia para determinar el nivel de los recorridos de A hasta D, para ambos casos.

Matriz de adyacencia

A B C D E FA 0 1 0 0 1 1B 0 0 0 0 1 0C 0 1 0 1 0 0D 0 0 0 0 0 0E 1 0 0 0 0 1F 1 0 1 1 0 0

2. Aplique las iteraciones apropiadas del algoritmo de DIJKSTRA, para hallar la ruta mínima desde el nodo 1 hasta el 8, para el siguiente grafo.

Camino Corto =1 al 8 8 + 7 + 3 + 1 =19

5. Para cada uno de los siguientes arboles escriba las respectivas expresiones de los recorridos, pre-orden, In_orden y Post_orden. Implemente un algoritmo para uno de ellos, Represente el árbol de b como una lista doblemente enlazada.

PRE-ORDEN

/,^,*,+,^,b,3,^,a,2,^,a,1/2,2,*,4,+,*,3,a,^,b,/,x,2

Algotirmo

Void preoden (nodoarbol po){ If(po =!NULL)

{ Printf(“%3d” po -> dato);

Preorden (po ->izquierda); Preorden (po ->derecha); }

}

IN-ORDEN

b,^,3,+,a,^,2,*,a,^,1/2,^,2,/,4,*,3,*,a,+,b,^,x,/,2

Algotirmo

Void inorden (nodoarbol io){ If(io =!NULL)

{ Printf(“%3d” io -> dato);

Inorden (io ->raiz); Inorden (io ->izquierda); }

}