Tarea 5 de Análisis de Algoritmos

Trimestre 2012 Invierno
Entrega: 29 de marzo de 2012 a las 16:30 en mi oficina.

1. [10 puntos] Se tienen dos vectores de enteros positivos a = (a₁, a₂, ..., a_n) y b = (b₁, b₂, ..., b_n). Se desea permutar los elementos de b para obtener un tercer vector c = (c₁, c₂, ..., c_n) tal que el producto punto de a y c sea tan pequeño como sea posible. Recuerde que el producto punto de a y c está dado por a₁c₁ + a₂c₂ + ... + a_nc_n. Diseñe un algoritmo que encuentre el menor producto punto posible y demuestre que su algoritmo es correcto. Pista: haga algunos ejemplos a mano hasta que se dé cuenta de lo que está pasando.
   
2. [10 puntos] Muestre un ejemplo de una gráfica con costos positivos en sus aristas tales que al aplicar el algoritmo de Dijkstra el árbol de caminos más cortos no es un árbol abarcador de costo mínimo.
   
3. [10 puntos] Suponga que una gráfica conexa G = (V, E) tiene costos distintos en todas sus aristas. Demuestre que G tiene un único árbol abarcador de costo mínimo. Pista: ¿qué pasa cuando se le aplica el algoritmo de Prim o el algoritmo de Kruskal a esta gráfica?
   
4. [10 puntos] Suponga que una gráfica conexa G = (V, E) tiene costos distintos en todas sus aristas excepto por dos que tienen el mismo costo. ¿Será cierto que G tiene un único árbol abarcador de costo mínimo? Dé una demostración de que es verdadero o un ejemplo que muestre que es falso.