Primer Parcial 20/05/2006 (Algoritmos III)

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


1)
2)
Sup. que hay mas de un vertice con din = 0. Sea v uno de esos vertices. Como G es completo, v esta dirigido a todos los demas. Pero esto implica que el resto de los vertices tienen din >= 1 0, y esto contradice HI (habia mas de uno con din = 0) -> ABS
Para el caso de dout = 0 se prueba analogamente.


3)
=>) Sup. que G tiene un subgrafo S inducido donde todos sus vertices tienen grado >=2 -> La suma de grados de S es ΣdS(v) >= 2*nS. Pero como todo bosque tiene n-k ejes (siendo k la # de comp. conexas) -> ΣdS(v) = 2*(nS-k) < 2*nS -> ABS
<=) Sup. que G no es bosque -> G tiene algun ciclo. Sea S el subgrafo inducido que contiene a ese ciclo. Entonces todos los vertices que contiene S deben tener grado al menos grado 2. Pero por HI todo subgrafo inducido debe tener un vertice de grado 0 o 1 -> ABS


4)