Segundo Parcial 08/02/2010 (Algoritmos III)

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

1) Sea T un arbol. Probar que T tiene un matching perfecto entonces en el grafo resultante de sacar un vertice cualquiera de T xiste una componente conexa con cantidad impar de nodos y es la unica con esa propiedad.
2) Se construyo una ciudad especial para ratones, donde se va a realizar una competencia. El juego consiste en lo siguiente: los ratones salen todos de un mismo lugar, "La Salida" y deben llegar al otro extremo, donde los espera un rico queso (el aroma a queso los guia para saber hacia donde deben ir). Cuando un raton pasa por alguna esquina (lugar de encuentro de almenos dos caminos), este "marca" su territorio como propio, dejando un olor que impide a otros ratones pasar por esa esquin.

(a) Se quiere saber cual es la maxima cantidad de ratones que pueden jugar y llegar a destino.Modelar la situacion como un problema de grafos y proponer un algoritmo para resolver el problema. Decir su complejidad.

(b) Si se suelten los ratones y se los deja avanzar para donde quieran (asumiento que siempre saben donde esta el queso). Siempre van a poder llegar todos? JUSTIFICAR LA RESPUESTA

3) Demuestre que,dado un grafo conexo y planar, entonces chi(G) <= 5.

4) Probar que, para todo grafo F, chi(G) <= (chi(G)-1) <= 2m.
5)
(a) Probar que el problema de particion en subgrafos hamiltonianos es NP-completo. Particiones de subgrafos hamiltonianos : Dado un grafo G=(V,E) y un entero k,decidir si existeuna particion de V en k partes V1,...,Vk tales que el subgrafo inducido por cada V_i es hamiltoniano.
(b) Si el problema de Particion en subgrafos hamiltonianos se reduce polinomialmente al problema de decidir si existe un camino euleriano en un grafo, entonces:
Podemos decir que todo problema NP-hard es NP-Completo?
Si probamos ademas que Particion en subgrafos hamiltonianos esta en NP, Podemos decir que es NP-Completo? JUSTIFICAR