6. Demuestre que el algoritmo 9.4.3 examina (n3) aristas en el peor caso.
Algoritmo 9.4.6
Versión alternativa del algoritmo de Prim
Este algoritmo encuentra un árbol de expansión mínima en un gráfica G conexa ponderada. En cada paso, algunos vértices tienen etiquetas temporales y otros tienen etiquetas permanentes. La etiqueta de un vértice i se denota por Li. Entrada: Gráfica conexa ponderada con vértices 1, . . . , n y vértice inicial s. Si (i, j) es una arista, w(i, j) es igual al peso de (i, j); si (i, j) no es una arista, w(i, j) es igual a ∞ (un valor mayor que cualquier peso real) Salida: Árbol de expansión mínima T
7. Muestre la manera en que el algoritmo 9.4.6 encuentra un árbol de expansión mínima para las gráficas de los ejercicios 1 al 5.
8. Demuestre que el algoritmo 9.4.6 examina (n2) aristas en el peor caso.
9. Pruebe que el algoritmo 9.4.6 es correcto; es decir, al terminar el algoritmo, T es un árbol de expansión mínima.
10. Sea G una gráfica conexa ponderada, sea v un vértice en G y sea e la arista con peso mínimo incidente en v. Demuestre que e está contenida en algún árbol de expansión mínima.
11. Sea G una gráfica conexa ponderada y sea v un vértice en G. Suponga que los pesos de las aristas incidentes en v son distintos. Sea e la arista con peso mínimo incidente en v. ¿Debe e estar contenida en todo árbol de expansión mínima?
12. Demuestre que cualquier algoritmo que encuentra un árbol de expansión mínima en Kn, cuando todos los pesos son iguales, debe examinar toda arista en Kn.
13. Demuestre que si todos los pesos en una gráfica conexa G son diferentes, G tiene un árbol de expansión mínima.
En los ejercicios 14 al 16, decida si la afirmación es falsa o verdadera. Si es verdadera, pruébela; de otra manera, dé un contraejemplo. En cada ejercicio, G es una gráfica conexa y ponderada.
14. Si todos los pesos en G son distintos, los árboles de expansión de G diferentes tienen pesos diferentes.
15. Si e es una arista en G cuyo peso es menor que el peso de cada tercera arista, e está en todo árbol de mínima expansión de G.
16. Si T es un árbol de expansión mínima de G, existe un etiquetado de los vértices de G de manera que el algoritmo 9.4.3 produce T.
17. Sea G una gráfica conexa ponderada. Demuestre que si, mientras sea posible, se elimina una arista de G con peso máximo y cuya eliminación no desconecta a G, el resultado es un árbol de expansión mínima para G.
18. Escriba un algoritmo que encuentre un árbol de expansión mínima en una gráfica conexa ponderada.
19. Pruebe que su algoritmo del ejercicio 18 es correcto. El algoritmo de Kruskal encuentra un árbol de expansión mínimo en una gráfica G conexa ponderada que tiene n vértices como sigue. La gráfica Tinicialmente consiste en los vértices de G y ninguna arista. En cada iteración, se agrega una arista e a Tcon peso mínimo que no completa un ciclo en T. Cuando T tiene n −1 aristas, se detiene.
20. Establezca formalmente el algoritmo de Kruskal.
21. Muestre cómo el algoritmo de Kruskal encuentra árboles de expansión mínima para las gráficas de los ejercicios 1 al 5.
22. Demuestre que el algoritmo de Kruskal es correcto; es decir, al terminar el algoritmo de Kruskal, T es un árbol de expansión mínima.
23. Sea V un conjunto de n vértices y sea s una “función de disimilitud” en V×V (vea el ejemplo 8.1.7). Sea G la gráfica ponderada completa que tiene vértices V y pesos w(vi, vj) =s(vi, vj). Modifique el algoritmo de Kruskal de manera que agrupe datos en clases. Esta modificación se conoce como método del vecino más cercano (vea [Gosel]).
Los ejercicios 24 al 30 se refieren a la siguiente situación. Suponga que tenemos timbres de varias denominaciones y queremos elegir el mínimo número de timbres para completar una cantidad dada de importe postal. Considere un algoritmo ambicioso que selecciona timbres escogiendo todos los que puede de la denominación más grande, después todos los que puede de la denominación siguiente más grande, y así sucesivamente.
24. Demuestre que si las denominaciones disponibles son 1, 8 y 10 centavos, el algoritmo no siempre produce el menor número de timbres para completar un importe postal dado.
25. Demuestre que si las denominaciones disponibles son 1, 5 y 25 centavos, el algoritmo produce el menor número de timbres para completar un importe dado.
26. Encuentre enteros positivos a1 y a2 tales que a1 > 2a2 > 1, a2 no divide a a1 y el algoritmo, con denominaciones disponibles 1, a1, a2, no siempre produce el menor número de timbres para completar el importe postal.
27. Encuentre enteros positivos a1 y a2 tales que a1 > 2a2 > 1, a2 no divide a a1 y el algoritmo, con denominaciones disponibles 1, a1, a2, produce el menor número de timbres para completar cualquier importe postal dado. Pruebe que sus valores en realidad dan una solución óptima.
28. Suponga que las denominaciones disponibles son
1=a1 < a2 < ···< an.
Demuestre, dando un contraejemplo, que la condición
ai ≥2ai−1 −ai−2,3 ≤i ≤n,
no es necesaria ni suficiente para que el algoritmo ambicioso sea óptimo.
29. Demuestre que el algoritmo ambicioso es óptimo para las denominaciones
1=a1 < a2 < ···< am
si y sólo si ese algoritmo es óptimo para todas las denominaciones menores que am−1+am. (Este resultado se debe a William Seaman).
30. Demuestre que la cota am−1 + am en el ejercicio 29 no puede ser menor.
