Final del 08/03/18 (Algoritmos III)

Final escrito tomado por Paula Zabala. Iba a ser oral, pero eramos muchos. Nos dio la opción de leerlo e intentar hacerlo e irnos sin entregar si no estábamos convencidos.

Ejercicio 1

A) Nombrar las técnicas algorítmicas vistas en la materia. B) Describir alguna de ellas

Ejercicio 2

Dar cotas superiores e inferiores para el número cromático de un grafo.

Ejercicio 3

Se tiene un árbol sin raíz, se quiere elegir como raíz aquel nodo tal que se maximize la altura del árbol, ¿como eligirias el nodo? ¿Y si quiero minimizar la altura?

Ejercicio 4

A) enunciar el invariante del algoritmo de Dantzig B) Enumerar diferencias entre el algoritmo de Dantzig y el algoritmo de Floyd

Ejercicio 5

Un arco vital máximo es aquel que dado una red de flujo al eliminarlo la reducción total de flujo de la red se reduce más que si elimino cualquier otro arco. Decidir si las siguientes afirmaciones son V o F, justificar:

A) el arco vital máximo es aquel de máxima capacidad B) el arco vital máximo es aquel de máximo flujo C) el arco vital máximo es aquel de máximo flujo entre aquellos arcos que pertenecen a un corte mínimo de la red D) el arco vital máximo debe pertenecer a un corte mínimo de la red E) el arco vital máximo es unico