Primer Parcial 15/10/2005 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia


1)
Si G no tiene ciclos -> G es un bosque -> Sus comp. conexas son arboles -> La cant. de ejes de cada una es ni-1 i en 1..k. Con lo cual la cant. total de ejes de G es:
Σ{i=1..k} ni-1 = Σ{i=1..k} ni - Σ{i=1..k} 1 = n-k


2)
Sup. que G contiene como subgrafo inducido a un camino simple de 4 nodos. Pero entonces en el complemento, ese camino simple no se separa en otras comp. conexas, con lo cual no hay forma de llevarlo a un conj. de vertices de grado 0 -> ABS


3)
Sup eMax_TMin > eMax_T. Sea TMin el AGM de G. Separemos TMin en dos conj. de vertices: A y B, tq esten unidos por eMax_TMin. Luego hacemos lo mismo con T, en los mismos A y B, entonces aqui estaran unidos por una arista que llamaremos e. Entonces se cumple esta relacion: e <= eMax_T < eMax_TMin. Pero esto significa que si se reemplaza en TMin la arista eMax_TMin por e, se obtiene un AG de menor peso que el AGM -> ABS


4)
a) Corriendo el algoritmo de Floyd:

. a b c  Pasando por {}
a 0 2 ∞
b ∞0 -1
c 2 3 0

. a b c  Pasando por {a}
a 0 2 ∞
b ∞0 -1
c 2 3 0

. a b c  Pasando por {a,b}
a 0 2 1
b ∞0 -1
c 2 3 0

. a b c  Pasando por {a,b,c}
a 0 2 1
b 1 0 -1
c 2 3 0


b)


5)