Primer Parcial 17/12/2003 (Algoritmos III)

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


1)
Sean v,w los unicos dos vertices de grado impar. Sup. que no hay camino entre ellos. Entonces se puede separar el grafo en 2 componentes conexas: C1 U {v}, y C2 U {w}. Pero entonces la suma de grados de ambas comp. conexas son:
Σ{x en C1} d(x) + d(v) = Par + Impar = Impar
Σ{x en C2} d(x) + d(w) = Par + Impar = Impar
Con lo cual no se cumple la propiedad de los grafos -> ABS


2)
a)Parando Dijkstra se obtienen k caminos desde el vertice inicial a k vertices distintos
b)Parando Dantzig se obtienen todos los caminos entre todo par de vertices solo considerando k vertices
c)Parando Floyd se obtiene lo mismo que en Dantzig, pero sin tomar el "grafo inducido"


3)
Sup. no existe AGM de G que contiene a e. Sea e' otro eje incidente a x.
Sea T un AGM, T'=T+e (de manera que T' tiene exactamente un ciclo, en el que esta e) y T"=T'-e' (como T" es conexo y V(G)=V(T") -> T" es AG de G). Entonces:
L(T") = L(T')-w(e') = [ L(T)+w(e) ]-w(e') <= (HI) L(T) -> Existe AGM de G que contiene a e -> ABS


4) (Revisar)
a) Si G no es conexo, vale para toda comp. conexa Ci:
Como Ci es conexa -> tiene un arbol generador. Como todo arbol tiene al menos 2 hojas y un vertice de corte no puede ser hoja de un AG -> Ci tiene al menos 2 vertices no de corte


b)
c)


5)