1. No category

Instituto de Computación - Facultad de Ingeniería
Programación 3 - Curso 2015 - Tarea 1
Programación 3 - Curso 2015
Tarea 1 - Cuarta Entrega
1.
Objetivos
Manejo y diseño de grafos: recorridas, conexión fuerte, componentes fuertemente conexas y orden topológico.
2.
Conocimientos previos
Grafos
3.
Ejercicio
Sea G un grafo dirigido y GC su grafo de componentes.
1. Considere una DFS de G en la cual los vértices son apilados en una pila P al terminar de ser procesados. Para cada CFC Ci sea fi , 1 ≤ i ≤ k , el primer vértice visitado, y sea fk , · · · , f1 el orden en que
esos vértices son apilados en P . Demuestre:
a) Si en una recorrida DFS el vértice fi es visitado antes que el vértice fj y hay un camino desde fi
hacia fj , entonces fi será apilado después de fj .
b) Para cada CFC Ci , fi es el último de sus vértices que se apila en P .
c) Si hay algún camino desde la CFC Ci a la CFC Cj , entonces fi se apila en P después que fj .
d) Al terminar la DFS el vértice que queda en el tope de P pertenece a una CFC fuente.
e) En el proceso de desapilar P , la secuencia f1 , · · · , fk determina una secuencia v = (v1 , · · · , vk )
que es un ordenamiento topológico de GC , donde vi representa a la CFC Ci .
2. Describa y justifique un algoritmo que permita encontrar cada una de las CFCs de G.
4.
Problema basado en la realidad
Otro de los colaboradores, Dippy First Sershi, dice que no hace falta conseguir el diagrama sugerido
por Topo (visto en la tercera entrega) y que él puede lograr la reconstrucción de las colecciones. ¿Puede
resolverse el problema sin encontrar el diagrama? ¿Cómo puede hacerlo First sin encontrar el diagrama?
5.
Entregas en clase
La solución debe incluir lo siguiente:
1. Solución del ejercicio.
2. Descripción de como encontrar las colecciones teniendo solo la información original: artículos y referencias entre ellos.
3. Seudocódigo que encuentre el grado de separación de una colección dada. Se define grado de separación de una colección como la máxima separación entre dos artículos de la misma.
Se debe entregar la solución antes del lunes 14 de setiembre a las 17:00 vía EVA. El archivo debe estar
en formato PDF y debe llamarse G-1-4.pdf, donde G es el número del grupo. Además se debe entregar
una copia impresa en la clase de monitoreo de esa semana.
1