Matematica

IN77O: Modelos y Algoritmos de Optimizaci´n o Profesores : Cristi´n Cort´s, Daniel Espinoza a e Auxiliares : Jos´ Mu~oz, Rodrigo L´pez, Diego Mor´n e n o a

Ejercicios resueltos 1
Martes 05 de Abril de 2009

P1.- Sea G = (A, N ) un grafo dirigido. Suponga que los costos de los arcos satisfacen aij ≥
0, ∀(i, j) ∈ A. Considere el problema de rutas m´ ınimas uno-a-todos resuelto con alg´nm´todo de Label u e Setting, pero en el que s´lo se est´ interesado en conocer la ruta m´s corta del nodo 1 a un o a a subconjunto T de nodos. Sea a = m´ it : (i, t) ∈ A, t ∈ T } ın{a Si a > 0, demuestre que se puede detener el m´todo cuando uno de los nodos de m´ e ınima etiqueta en la lista V , que denotaremos J, tiene una etiqueta dJ que cumple: dJ + a > m´x{ds : s ∈ T } (∗) a

Sol: Es bueno teneren cuenta de que estamos aplicando el Algoritmo de Dijkstra con costos
positivos, es decir, el caso interesante, pues se cumplen las buenas propiedades :D. Basados en la observaci´n anterior, de (∗) podemos concluir que, dado t ∈ T , entonces o dt ≤ m´x{ds : s ∈ T } < dJ + a < ∞ a es decir, todas las etiquetas de elementos en T se han modificado (pues son finitas). Luego, para un nodo t ∈ T setienen s´lo 2 posibles casos: t ∈ V ´ t sali´ de V (y por lo tanto o o o fue nodo de etiqueta m´ ınima en alg´n momento, por lo que no vuelve a entrar a V ). u Para probar que podemos detener el algoritmo, basta probar que, en ninguno de los 2 casos anteriores, las etiquetas de nodos en T ser´n modificadas. Veamos: a Si t sali´ V : por propiedad de Dijkstra con costos positivos, dt no se vuelve amodificar o (ya que en alguna etapa anterior t fue el nodo de etiqueta m´ ınima que sali´ de V ). o Si t ∈ V : La unica forma de que la etiqueta de un nodo cualquiera i ∈ V se modifique, ´ en la iteraci´n en que el nodo que sale de V es J, es que se cumpla: o di > dJ + aJi 1

Veamos que esto no se cumple para t ∈ T . Si se tuviera que: dt > dJ + aJt (∗∗)

podemos usar (∗∗), que dt ≤ m´x{ds : s ∈ T }y que a ≤ aJt para concluir que: a m´x{ds : s ∈ T } > dJ + a a lo que contradice (∗). Por lo tanto ning´n nodo en T puede cumplir (∗∗). u Con esto, si t ∈ T , entonces dt no se modifica en esta iteraci´n. o ¿Se modifican las etiquetas de los nodos en T en las iteraciones siguientes? La respuesta es no, pues si I ∈ V es el nodo que sale de V en la siguiente iteraci´n, este o nodo cumple: dJ ≤ dI puesJ ten´ etiqueta m´ ıa ınima en la iteraci´n anterior, cuando sali´ de V , y por propiedad o o de Dijkstra con costos positivos, las “etiquetas m´ ınimas” son de valor creciente a medida que se avanza en las iteraciones. Con esto, el nodo I tambi´n cumple la propiedad (∗). Luego, los nodos en T tampoco e cambian el valor de sus etiquetas en esta iteraci´n. o Conclusi´n: Al partir de la iteraci´nen que se cumple (∗) el valor las etiquetas dt , con o o t ∈ T no se modifican en ninguna de las iteraciones siguientes, y como estas etiquetas representan el valor del camino m´s corto desde el nodo 1 al nodo t (pues ya no ser´n a a modificadas), podemos dar por terminado el objetivo de encontrar todos los caminos m´s cortos desde 1 al subconjunto T de los nodos. a

2

P2.- Suponga que todoslos nodos de un grafo G tiene grado estrictamente mayor que uno. Pruebe
que G contiene al menos un ciclo. OBS: Notemos que esta fue la propiedad que usamos en la clase auxiliar 1 2007 para garantizar la existencia de un ciclo en uno de los pasos del algoritmo de la parte a) del problema.

Sol: A continuaci´n describiremos un algoritmo dise˜ado para encontrar un ciclo en el grafo G, lo o n
quenos permitir´ probar la propiedad: a

ALGORITMO Inicializaci´n: v0 ∈ N cualquiera, V = {v0 } conjunto de nodos visitados, P = v0 camino o auxiliar, C = ∅ para guardar el ciclo, u = v0 variable auxiliar. (1) Elegir un nodo w tal que (u, w) o (w, u) ∈ A. (2) Si w ∈ V / actualizar P = P w, u = w, V = V ∪ {w}. Volver a (1). En caso contrario hacer C = wvk+l . . . vk+l w (estamos suponiendo que P...