Analisis_de_grafos

Vista previa del material en texto

POLITÉCNICO INTERNACIONAL 
DESARROLLO DE SOFTWARE Y APLICACIONES 
MÓVILES 
DISEÑO DE ALGORTIMOS lI 
 
 DISEÑO DE GRAFOS 
Realizado por: Sara Alexandra Castrillón Garcés 
 
 
 
Presentado a: Ricardo Augusto Castelbanco 
Sepulveda 
NOTA: Al imprimir el presente documento, se convierte en COPIA NO CONTROLADA, a menos que se identifique como COPIA CONTROLADA. 
 
 
 FORMATO Código: PI-GA-FT-007 
ACTIVIDAD DE APRENDIZAJE 
Emisión: 27/08/2019 
Versión: 01 
 
 
Nombre de la actividad 
• Análisis de Grafos 
 
 
Objetivo de la actividad 
• Implementar el análisis de grafos en la solución de problemas identificando la ruta 
más corta, la ruta más larga, y la cantidad de caminos posibles 
 
Descripción e instrucciones para realizar la actividad 
Lee el material denominado: Teoría de Grafos que se encuentra en el núcleo. 
Problemática 
La empresa Edmsoft -de desarrollo de software- quiere incursionar en la implementación 
de redes de computadoras para identificar cuál es la ruta más corta que seguirá un paquete 
de datos, a través de los nodos principales (routers) de la red. Para empezar a comprender 
el asunto de las rutas mas cortas, Edmsoft analiza un mapa de carreteras de España, que 
en términos abstractos y generales sería similar a un mapa que ilustra las ubicaciones de 
los nodos principales (routers) de una red de telecomunicaciones WAN. En la figura 1 se 
observa un grafo de carreteras entre ciudades de España. 
Figura 1. Grafo de Carreteras entre Ciudades de España 
 
 
 
Fuente: Sancho, F. (12 de octubre de 2019). 
NOTA: Al imprimir el presente documento, se convierte en COPIA NO CONTROLADA, a menos que se identifique como COPIA CONTROLADA. 
 
 
 FORMATO Código: PI-GA-FT-007 
ACTIVIDAD DE APRENDIZAJE 
Emisión: 27/08/2019 
Versión: 01 
 
 
Para ir entrenándose en los asuntos de determinar la ruta más corta para un paquete de 
datos entre dos nodos o vértices, la empresa edmsoft quiere determinar la ruta más corta 
entre ciudades, y de igual manera, la distancia más larga entre ciudades, así como la 
cantidad de caminos existentes entre dos ciudades. Su labor como desarrollador de 
software de la empresa Edmsoft, y con conocimientos en el tema de grafos será realizar las 
siguientes actividades: 
• Determina el camino más corto de Murcia a Badajoz. Argumenta y 
explica el procedimiento utilizado para llegar a la conclusión. 
 
Procedimiento: Para determinar el camino más corto de Murcia a Bajadoz, se parte de lo 
siguiente, mirando gráficamente: 
 
PASO 1 : 
Se procede a determinar los posibles caminos de Murcia a Bajadoz, determinando las dos 
distancias más cortas, que se pueden ver, así las posibilidades se resaltarán con azul 
en aristas y vértices pertenecientes a la solución momentánea y con rojo aristas y vértices 
candidatos 
 
 
 
 
 
 
 
 
 
 
 
PASO 2 
Se determinan los caminos gráficamente y se muestran las distancias para llegar de una 
ciudad a otra pasando por sus vértices. 
➢ Camino Amarillo: Murcia-Albacete-Madrid-Bajadoz 
➢ Camino Verde: Mucia-Granada-Jáen-Madrid -Bajadoz 
 
PASO 3: 
Se efectúa la suma de las distancias y se obtienen los siguientes resultados: 
 
➢ Amarillo: 804 
 
➢ Verde: 1115 
NOTA: Al imprimir el presente documento, se convierte en COPIA NO CONTROLADA, a menos que se identifique como COPIA CONTROLADA. 
 
 
 FORMATO Código: PI-GA-FT-007 
ACTIVIDAD DE APRENDIZAJE 
Emisión: 27/08/2019 
Versión: 01 
 
 
 
 
 
Sin embargo, para tener certeza de la conclusión, se tendrá en cuenta el trabajo del camino 
más corto en el cual se emplea el algoritmo de Dijkstra así: 
 
 
 
 
 
 
 
 
 
 
 
Se adjudican letras a cada una de las ciudades, de la siguiente manera: 
➢ A: Murcia , 
➢ B: Albacele, 
➢ C: Madrid, 
➢ D: Granada, 
➢ E: Jaén, 
➢ F: Bajadoz. 
 
Paso 1: 
 se hace revisión de los vértices adyacentes del punto A, y se resalta la distancia más baja 
como definitiva. 
 
Paso 2: 
 se revisa cual es la de menor distancia y se transcribe en la columna paso 2 y se sombrea como definitiva, 
se marca * para quienes no incidirán en pasos siguientes y se marca símbolo ∞ para los 
vértices que no son adyacentes. 
 
Paso 3: 
 se revisa menor distancia y numero de pasos, para determinar la distancia más corta y se 
sombrea como definitiva; se marca * para quienes no incidirán en pasos siguientes y se 
marca símbolo 
∞ para los vértices que no son adyacentes 
 
 
 
 
 
NOTA: Al imprimir el presente documento, se convierte en COPIA NO CONTROLADA, a menos que se identifique como COPIA CONTROLADA. 
 
 
 FORMATO Código: PI-GA-FT-007 
ACTIVIDAD DE APRENDIZAJE 
Emisión: 27/08/2019 
Versión: 01 
 
 
. 
Paso 4: 
 se revisa menor distancia y numero de pasos, como existe un camino con un paso adicional 
se transcribe la distancia y se analiza el paso siguiente para determinar la distancia más corta 
y se sombrea como definitiva; se marca * para quienes no incidirán en pasos siguientes y 
se marca símbolo 
∞ para los vértices que no son adyacentes. 
 
Paso 5: 
 se revisa menor distancia y numero de pasos, se transcribe la distancia y se observa el 
menor valor teniendo en cuenta que deben pasar por una ciudad que es convergente a los 
dos caminos que para el caso es el punto C, se observa la corresponsabilidad de adyacencia 
para determinar la distancia más corta y se sombrea como definitiva, se resume en el cuadro 
siguiente: 
 
 
Vértice Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 
A (0,A) * * * * 
B (150,A) (150,A) * * * 
C ∞ (401,B) (401,B) (401,B) (804,F) 
D (278,A) (278,A) * * * 
E ∞ (377,D) (377,D) (732,C) ∞ 
F ∞ ∞ ∞ ∞ (1135,F) 
 
 
CONCLUSIÓN: 
El camino más corto es el camino Amarillo: Murcia-Albacete-Madrid-Bajadoz. 
 
• Determina la ciudad más lejana de Barcelona. Argumenta y explica el 
procedimiento utilizado para llegar a la conclusión. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
NOTA: Al imprimir el presente documento, se convierte en COPIA NO CONTROLADA, a menos que se identifique como COPIA CONTROLADA. 
 
 
 FORMATO Código: PI-GA-FT-007 
ACTIVIDAD DE APRENDIZAJE 
Emisión: 27/08/2019 
Versión: 01 
 
 
 
PASO 1 
Se procede a determinar los posibles caminos de Barcelona a las ciudades más distantes en 
el mapa, determinando las distancias más largas, que se pueden ver, así las posibilidades se 
resaltarán con morado, amarillo y verde en aristas y vértices pertenecientes a las posibles 
soluciones. 
 
PASO 2 
Se determinan los caminos gráficamente y se muestran las distancias para llegar de 
una ciudad a otra pasando por sus vértices. 
➢ Morado camino: Barcelona-Zaragoza-Madrid-Valladolid-Coruña 
➢ Verde camino: Barcelona-Zaragoza-Madrid-Bajadoz 
➢ Amarillo camino: Barcelona-Valencia-Murcia-Granada-Sevilla-Cadiz 
 
PASO 3: 
Se efectúa la suma de las distancias y se obtienen los siguientes resultados: 
 
➢ Morado: 1269 
 
➢ Verde: 1024 
 
➢ Amarillo: 1249 
 
 
CONCLUSIÓN: La ciudad más distante es Coruña, camino Morado: Barcelona-Zaragoza-
Madrid-Valladolid-Coruña. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
NOTA: Al imprimir el presente documento, se convierte en COPIA NO CONTROLADA, a menos que se identifique como COPIA CONTROLADA. 
 
 
 FORMATO Código: PI-GA-FT-007 
ACTIVIDAD DE APRENDIZAJE 
Emisión: 27/08/2019 
Versión: 01 
 
 
• Determina cuántos caminos distintos existen de Sevilla a Zaragoza. 
Argumenta y explica el procedimiento utilizado para llegar a la conclusión. 
 
Para determinar el número de caminos de Sevilla a Zaragoza, se usa el siguiente proceso, 
teniendo en cuenta que es una sucesión finita de vértices, entonces: 
 
C: camino 
CONCLUSIÓN: Total caminos de Sevilla a Zaragoza: 8 
 
NOTA: Al imprimir el presente documento, se convierte en COPIA NO CONTROLADA, a menos que se identifique como COPIA CONTROLADA. 
 
 
 FORMATO Código: PI-GA-FT-007 
ACTIVIDAD DE APRENDIZAJE 
Emisión: 27/08/2019 
Versión: 01