Segundo Parcial 21/12/2009 (Algoritmos III)

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


1) Tenemos 9 equipos de futbol en un torneo, donde juegan TODOS CONTA TODOS. Cada equipo i, no puede recibir mas de xi goles. Por otro lado , cada equipo no puede realizar mas de zi goles en total. Decidir si puede haber un torneo tal que el total de goles realizados entre todos los equipos sea 19. En caso de existir, decir cuantos goles realiza cada equipo y a contra quien, en caso de no existir probar que efectivamente no existe. Resolver el problema modelando este problema de grafos.

i z_i x_i
1 3 2
2 4 1
3 1 3
4 9 11
5 2 2


EL grado de planaridad PL(G) se define como la minima cantidad de aristas que hay que sacarle a G para que G quede planar.
(a) Mostrar que si G tiene n vertices y m aristas, entonces PL(G) >= m-3n+6
(b) Determinar PL(K3,3) y PL(k6)


3) Cuantas palabras distintas de longitud 7 se pueden formar con k letras de tal manera que dos letras consecutivas sean distintas y que ademas, la letra de la posicion central sea distinta a las letras de la primer posicion y de la ultima posicion? Modelar el problema como un problema de coloreo. Dar el valor cuando k=4.


4) Supongamos M es un matching maximal. Probar que para todo G, delta(G) <= 2M (Sugerencia : considerar por separado, el caso en que M es perfecto y el caso en que M no es perfecto, pero es maximal).


5) Problema de COLOREO: Dado G, decidir si G puede colorearse con a lo sumo k colores. Supongamos que PI_1 se resuleve en forma polinomial, y encontramos una reduccion polinomial f del problema de coloreo PI_1. Decidir cuales afirmacion podemos asegurar que son verdaderas. JUSTIFICAR TODO.
(a) COloreo se resuelve en forma polinomial
(b) Todo problema de NP se reduce a PI_1
(c) Todo problema NP-completo se reduce a PI_1
(d) Si sabemos resolver el problema de coloreo en tiempo polinomial con un algoritmo p, entonces el algoritmo que resulta de aplicar primero f y luego p es un algoritmo polinomial para resolver PI_1
(e) Todo problema NP-hard se reduce a PI_1
(f) Existe una tranformacion polinomial de PI_1 a coloreo.
(g) NP=co-NP