ALGORITMOS PYTHON-páginas-50

Vista previa del material en texto

[228]
Guía de ejercicios prácticos
A continuación se plantean una serie de problemas, que se deberán resolver utilizando el TDA gra-
fo, para lo cual se implementarán grafos dirigidos salvo que el ejercicio indique lo contrario.
1. Generar un grafo con 15 vértices aleatorios no repetidos (con números de 1 a 100), luego agregar 
30 aristas –no repetidas– que conecten vértices de manera aleatoria, con etiquetas –también 
aleatorias– dentro del rango de 1 a 100, después resolver las siguientes actividades:
a. primero eliminar los vértices que hayan quedado desconectados, es decir, que ningún otro 
vértice tenga una arista que lo apunte y que de él no salga ninguna arista;
b. determinar el nodo con mayor cantidad de aristas que salen de él, puede ser más de uno;
c. determinar el nodo con mayor cantidad de aristas que llegan a él, puede ser más de uno;
d. indicar los vértices desde los cuales no se puede acceder a otro vértice;
e. contar cuantos vértice componen el grafo, dado que se genera aleatoriamente y se elimi-
nan los vértices que quedan desconectados;
f. determinar cuántos vértices tienen un arista a sí mismo, es decir, un ciclo directo;
g. determinar la arista más larga, indicando su origen, destino y valor –puede ser más de una.
2. Sobre el siguiente dígrafo implementar los algoritmos necesarios para resolver las tareas que 
se presentan a continuación:
a. represéntelo como arreglo de listas de adyacencias y lista de listas de adyacencia;
b. cargue el valor de las etiquetas de todas las aristas;
c. encuentre el árbol de expansión mínima, para este punto considere el grafo como no dirigido;
d. agregue un arco de E hasta C;
e. encuentre el camino más corto de A hasta D.
[229]
3. Implementar un grafo no dirigido que permita cargar puertos y las aristas que conecten dichos 
puertos, que permita resolver las siguientes tareas:
a. cada arista debe tener la distancia que separa dichos puertos;
b. realizar un barrido en profundidad desde el primer puerto en el grafo;
c. determinar el camino más corto desde puerto Madero al puerto de Rodas;
d. determinar el puerto con mayor número de aristas y eliminarlo.
4. Un empresa de telefonía celular dispone de la información de sus antenas, de las cuales se 
conoce: su ubicación (latitud y longitud), código de identificación, velocidad de transferencia 
en megabytes/segundos, y además las antenas a las que transmite y las distancias a cada una de 
estas. Implementar un algoritmo que permita resolver los siguientes requerimientos:
a. utilizar un grafo no dirigido;
b. cargar la información de antenas y la relación con las demás;
c. determinar el tamaño del grafo;
d. determinar el camino más corto para transmitir desde la antena ubicada en la capital de 
Mendoza a la antena ubicada en la capital de Misiones, utilizando el algoritmo de Dijkstra;
e. encontrar el árbol de expansión mínimo del grafo, utilizando Prim o Kruskal;
f. determinar si la antena con código “TGK-783” existe, de ser así mostrar toda su información.
5. Cargar el esquema de red de la siguiente figura en un grafo e implementar los algoritmos nece-
sarios para resolver las tareas, listadas a continuación:
a. cada nodo además del nombre del equipo deberá almacenar su tipo: pc, notebook, servi-
dor, router, switch, impresora;
b. realizar un barrido en profundidad y amplitud partiendo desde la tres notebook: 
Red Hat, Debian, Arch;
c. encontrar el camino más corto para enviar a imprimir un documento desde la pc: Manjaro, 
Red Hat, Fedora hasta la impresora;
d. encontrar el árbol de expansión mínima;
e. determinar desde que pc (no notebook) es el camino más corto hasta el servidor “Guaraní”;
f. indicar desde que computadora del switch 01 es el camino más corto 
al servidor “MongoDB”;
[230]
g. cambiar la conexión de la impresora al router 02 y vuelva a resolver el punto b;
h. debe utilizar un grafo no dirigido.
6. Partiendo del árbol genealógico de los dioses griegos que se observa en la imagen del ejercicio 
20 de la guía de árboles (capítulo X), convertirlo en un grafo y resolver las siguientes actividades:
a. además del nombre de los dioses, deberá cargar una breve descripción de quien es o lo que 
representa, no más de 20 palabras;
b. deberá cargar todas las relaciones entre los distintos dioses: padre, madre, hijo, hermano, 
pareja, la etiquetas de dichas aristas son estos nombre de relación.
c. dado el nombre de un dios mostrar los hijos de este;
d. dado el nombre de un dios mostrar su nombre, padre, madre, hermanos y sus hijos;
e. determinar si existe relación directa entre dos vértice cualquieras, de ser así cual es la rela-
ción entre ambos;
f. dados dos dioses determinar el camino más corto entre estos y mostrarlo. Considere como 
camino más corto el que tenga menor número de aristas;
g. realizar un barrido en profundidad y amplitud de dicho grafo;
h. realizar un barrido mostrando el nombre de cada dios y el de su madre;
i. mostrar todos los ancestros de un determinado dios;
[231]
j. mostrar todos los nietos de Cronos;
k. mostrar todos los hijos de Tea;
l. persista los datos del grafo en archivos, uno para los vértices y otro para las aristas.
7. Implementar los algoritmos necesarios para resolver las siguientes tareas sobre el grafo de la figura:
a. barrido en profundidad y amplitud partiendo de A, C, F;
b. el camino más corto de A hasta F, de C hasta D, de B hasta G;
c. agrega una arista de C hasta A, de C hasta B, de G hasta D y vuelva a ejecutar los puntos del 
ítem anterior sin camino;
d. realice la representación de matriz de adyacencia del grafo.
8. Implementar un grafo social y los algoritmos necesarios para atender 
los siguientes requerimientos:
a. cargar personas como vértices del grafo;
b. cargar aristas con las siguientes etiquetas: Twitter, Instagram, Facebook y la cantidad de re-
twitters y me gusta respectivamente, que representan si la persona del vértice origen sigue 
o es amigo de la persona del vértice destino;
c. hallar el árbol de expansión máximo para cada red social –considere el grafo como no dirigi-
do para este punto–, es decir que las conexiones deben ser las de mayor peso –ósea el segui-
dor que tenga mayor interacción –; para lo cual si desea utilizar Prim o Kruskal sin modificar 
el código, puede determinar la arista de mayor peso entonces cuando aplique estos algoritmo 
el peso de cada arista será la arista de mayor peso menos el peso de la arista;
d. determine si es posible conectar la persona Guido Rossum con Mark Hamill a través de la 
red social Twitter;
[232]
e. determine si es posible conectar la persona Tom Holland con Robert Downey a través de 
cualquier red social;
f. indique a todas las personas que sigue a través de su red de Instagram la persona Daisy Rid-
ley.
9. Implementar un grafo no dirigido que permita administrar vuelos internacionales contem-
plando los siguientes requerimientos:
a. de cada aeropuerto se conoce: su nombre, ubicación (latitud y longitud) y cantidad de pis-
tas;
b. cada arista representa un viaje de un aeropuerto a otro, en cada una de esta puede haber 
más de un vuelo, de los cuales se conoce: hora de salida, hora de arribo, nombre de la em-
presa, costo del pasaje –considere que todos los pasajes cuestan lo mismo –, duración del 
viaje y distancia en km;
c. debe persistir los datos del grafo en archivos;
d. el grafo debe contener los aeropuertos de los siguientes países: Argentina, China, Brasil, 
Tailandia, Grecia, Alemania, Francia, Estados Unidos, Japón y Jamaica;
e. calcular el camino más corto desde el aeropuerto de Argentina a Tailandia considerando 
los siguientes criterios:
I. menor distancia,
II. menor duración de tiempo,
III. menor costo,
IV. menor número de escalas.
f. determinar todos los aeropuertos a los que se puede arribar desde Grecia de manera direc-
ta o indirecta.
10. Generar un grafo no dirigido con planetas de Star Wars y diseñar los algoritmos necesarios 
para resolver las siguientes actividades:
a. los siguientes planetasdeben estar en el grafo: Alderaan, Endor, Dagobah, Hoth, Tatooine, 
Kamino, Naboo, Mustafar, Scarif, Bespin, agregue 7 más;
b. genere al menos 4 aristas para cada uno de los planetas del grafo, no puede haber nodos 
con arcos a sí mismo;
c. encuentre el árbol de expansión mínima en cuanto a costos para recorrer todos los planetas;
[233]
d. hallar el camino más corto desde:
I. Tatooine hasta Dagobah,
II. Alderaan hasta Endor,
III. Hoth hasta Tatooine;
e. determinar todos los planteas a los que se puede llegar desde Tatooine.
11. Construir un grafo de afinidad entre los superhéroes de la película “Capitán América: Civil 
War” y resuelva las siguientes tareas:
a. cada vértice representara un superhéroes y las arista el nivel de afinidad (de 1 a 10);
b. cargar los siguientes super héroes: Capitan America, Iron Man, Black Widow, Falcon, The 
Winter Soldier, War Machine, Spider-Man, Ant-Man, Black Panther,Hawkeye, Scarlet 
Witch, Vision;
c. obtener el árbol de expansión máximo del Team Cap (CapitanAmerica) y del Team Stark 
(IronMan), considerando solo las arista cuyo valor sea superior a 7;
d. obtener el árbol de expansión máximo completo de Black Widow y Black Panther.
12. Representar en un grafo no dirigido las actividades de un proyecto, en el cual los arcos repre-
sentan el tiempo de dicha tarea y cuáles son las que pueden realizarse a continuación, teniendo 
en cuenta lo siguiente:
a. además del tiempo las aristas deberá almacenar el nombre de la persona que la realiza –un 
vértice no puede tener más de una arista de la misma persona–;
b. determinar el tiempo total mínimo del proyecto, las personas que realizan cada tarea;
c. determinar el menor tiempo requerido partiendo desde la actividad “análisis de requeri-
mientos” hasta llegar a la actividad “presentación de mockups”;
d. indicar todas las tareas que puede realizar la persona Harry.
13. El servicio postal de su ciudad le solicita desarrollar un algoritmo para mejorar el recorrido de 
sus carteros, considerando las siguientes cuestiones:
a. cada vértice del grafo tendrá la dirección de los puntos de entrega, además si se trata de una 
carta o un paquete –en el caso de este último también se dispondrá del peso–;
b. cada arista tendrá las distancias entre los distintos puntos de entrega, debe utilizar un grafo 
no dirigido;
c. encontrar el árbol de expansión mínimo de acuerdo a las distancias de los puntos de entrega;
[234]
d. encontrar el árbol de expansión máximo de acuerdo al peso de la entrega –en el caso de ser 
una carta considerar como peso cero–.
14. Implementar sobre un grafo no dirigido los algoritmos necesario para dar solución a las si-
guientes tareas:
a. cada vértice representar un ambiente de una casa: cocina, comedor, cochera, quincho, 
baño 1, baño 2, habitación 1, habitación 2, sala de estar, terraza, patio;
b. cargar al menos tres aristas a cada vértice, y a dos de estas cárguele cinco, el peso de la aris-
ta es la distancia entre los ambientes, se debe cargar en metros;
c. obtener el árbol de expansión mínima y determine cuantos metros de cables se necesitan 
para conectar todos los ambientes;
d. determinar cuál es el camino más corto desde la habitación 1 hasta la sala de estar para 
determinar cuántos metros de cable de red se necesitan para conectar el router con el 
Smart Tv.
15. Se requiere implementar un grafo para almacenar las siete maravillas arquitectónicas moder-
nas y naturales del mundo, para lo cual se deben tener en cuenta las siguientes actividades:
a. de cada una de las maravillas se conoce su nombre, país de ubicación (puede ser más de 
uno en las naturales) y tipo (natural o arquitectónica);
b. cada una debe estar relacionada con las otras seis de su tipo, para lo que se debe almacenar 
la distancia que las separa;
c. hallar el árbol de expansión mínimo de cada tipo de las maravillas;
d. determinar si existen países que dispongan de maravillas arquitectónicas y naturales;
e. determinar si algún país tiene más de una maravilla del mismo tipo;
f. deberá utilizar un grafo no dirigido.
16. Implementar un grafo no dirigido para almacenar puntos turísticos de interés de un determi-
nado país teniendo en cuenta los siguientes requerimientos:
a. debe ser un grafo completo es decir que todos los vértices se deben conectar con todos;
b. cargar los siguientes lugares (con sus coordenadas de latitud y longitud) templos de: Ate-
nas (Partenón), Zeus (Olimpia), Hera (Olimpia), Apolo (Delfos),Poseidón (Sunión), Arte-
misa (Éfeso) y Teatro de Dionisio (Acrópolis)
c. hallar el árbol de expansión mínimo partiendo de cualquiera de estos lugares;