Segundo Parcial 06/12/2005 (Algoritmos III)

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


1)
2)
Sean e1..e|E| los ejes ordenados tal que forman un circ. euleriano en G. Entonces en L(G) existira un circ. hamiltoniano por los vertices que representan esos ejes (estaran conectados por como se tomo el circ. euleriano)


3)


4)


5)
a) Sup. que n<6. Como todos los vertices tienen grado 4, debe haber al menos 5 vertices. Entonces n=5. Pero esto significa que se tiene un K5 -> no es planar -> ABS
b) Ver parcial Diego++