## ACTIVIDAD15 AUTOEVALUACIÓN

## Repaso de la Unidad III

Descripción

Los ejercicios que se proponen tienen la finalidad de que realices un repaso de los temas de la Unidad III.

1. Dado el siguiente grafo:

(a) Escribe, en orden de selección, las aristas seleccionadas por el algoritmo de Prim sobre ese grafo.

(b) Lo mismo que el apartado (a) pero con el algoritmo de Kruskal.

2. Considérese la información registrada en una agencia de viajes referente a los vuelos existentes entre todos los aeropuertos del mundo. Supongamos que toda conexión aérea es de ida y vuelta. Queremos resolver el siguiente problema: Dados los aeropuertos A y B ¿Cual es el mínimo número de transbordos en un viaje aéreo de A a B?

(a) De los algoritmos de recorrido de grafos conocidos, cuál elegirías para resolver este problema y por qué. Indica cual sería la modificación pertinente del algoritmo elegido.

(b) ¿Cuál es la complejidad temporal de cada uno de los algoritmos sobre grafos que conoces que resuelvan este problema?

(c) En conclusión, cuál de ellos elegirías y por qué.

Valor 0%

###