Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Grafos

De Wikilibros, la colección de libros de texto de contenido libre.

Ejercicio 1[editar]

Diagramas PERT[editar]

Introducción[editar]

Los diagramas PERT representan la precedencia de las actividades en un proyecto.

  • Cada arco en el diagrama representa una actividad.
  • Cada nodo representa un "punto de precedencias"; esto significa que cada una de las actividades salientes de un nodo, deberán ser precedidas por todas las actividades entrantes en ese nodo.

Además de la información de precedencias, se cuenta con la duración de cada una de las actividades, y la fecha de inicio del proyecto, lo que permite calcular las fechas tempranas y tardías de inicio y fin de actividad, que se definen como:

Fecha temprana de inicio de actividad
es la fecha más temprana en la cual puede iniciarse la actividad. Resulta de tomar la máxima fecha temprana de fin de actividad de todas las actividades que la preceden.
Fecha temprana de fin de actividad
es la fecha más temprana en la cual puede finalizar la actividad. Resulta de sumar la duración de la actividad a su fecha temprana de inicio.
Fecha tardía de inicio de actividad
es la fecha más tardía en la cual puede iniciarse la actividad sin comprometer el tiempo de finalización del proyecto. Resulta de restar la duración de la actividad a su fecha tardía de fin.
Fecha tardía de fin de actividad
es la fecha más tardía en la cual puede finalizar la actividad sin comprometer el tiempo de finalización del proyecto. Resulta de tomar la mínima fecha tardía de inicio de actividad de todas las actividades que la suceden.

Requisitos de la representación gráfica[editar]

  • Los nodos de precedencia auxiliares que deban crearse generarán actividades ficticias, llamadas "dummy". Deberán etiquetarse con ese nombre, seguido de un número que las identifique.
  • Deberá simplificarse el grafo cuanto sea posible, de manera de obtener la menor cantidad de actividades ficticias posible.
  • Si dos actividades tienen el mismo nodo de origen y de destino, deberá generarse una precedencia ficticia que interrumpa una de ellas, y entre este nodo y el nodo de destino se creará una actividad ficticia.

Ejercicio 2[editar]

Agregue a la clase Grafo los siguientes métodos:

  • gradoPositivo(Nodo unNodo) : integer;

Retorna un entero que define el grado positivo del nodo argumento.

  • gradoNegativo(Nodo unNodo) : integer;

Retorna un entero que define el grado negativo del nodo argumento.

  • existeCiclo() : boolean;

Retorna true en caso que el grafo tenga al menos un camino cerrado.

Ejercicio 3[editar]

Principio de optimación

El principio de optimación establece que si el enrutador D se encuentra en la ruta optima entre los enrutadores A y M, entonces la ruta entre D y M es también la ruta optima entre ese par de enrutadores.

El grupo de trayectorias optimas de un origen O a todos los demás destinos, forma un árbol con raíz. O, llamado árbol de descenso.

Se le solicita que defina la clase Red, las instancias de esta clase representaran redes de computadoras. Las relaciones que existirán deberán ser entre routers, dejando el modelado de los hosts de una red en forma transparente para la implementación.

Las instancias deberán responder al siguiente protocolo:

  • agregarRouter(Router unRouter) : void;

Agregar un router a la red.

  • conectar(Router r1,Router router2) : void;

Conecta el router r1 con el router r2, siempre que ambos objetos pertenezcan a la red.

  • arbolDeDescenso(Router unRouter) : SList;

Método que retorna una instancia de la clase SList, donde cada elemento de la lista de retorno representa un árbol de descenso para el router argumento.

  • enlacesPuntoPunto(Router unRouter) : SList;

Retornar una lista de routers que son los enlaces punto a punto del router argumento.

  • caminos (Router router1,Router router2) : SList;

Retorna una lista con todos los caminos entre router1 y router2.

  • caminosOptimos(Router router1,Router router2) : SList;

Retorna una lista con todos los caminos óptimos entre router1 y router2.

Además deberá definir la clase para representar los objetos router, considere un protocolo básico para las instancias de esta clase, como por ejemplo:

  • conectar(Router unRouter) : void;
  • enlacesPuntoPunto() : SList;
  • camino(router unRouter) ;
  • darPaquete() : Paquete;
  • aceptarPaquete(Paquete unPaquete) : void;