Segundo Parcial 06/12/2006 (Algoritmos III)

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


1) Sea G un grafo y sea su polinomio cromatico. Probar que G no es planar.

Usando que G es planar -> X(G) <= 5, esto significa que hay alguna forma de colorear un grafo con 5 colores o menos -> PG(k) != 0 para algun k <= 5. Pero se puede ver que esto no pasa -> G no es planar


2) Considerar el siguiente problema: Marte ha desarrollado unas naves aeroespaciales que tienen la siguiente particularidad.
* Las naves viajan por rutas aereas que se generan en forma natural todos los 6 de diciembre, entre ALGUNOS centros cosmicos de energia que estan dispuestos en el espacio
* Cuando una nave va pasando por una de las rutas, esta ruta se va destruyendo automaticamente
* Las rutas entre los centros cosmicos son de la misma longitud y se pueden recorrer en cualquier direccion. Al recorrer cada ruta la nave se queda sin energia y precisa abastecerse de energia nuevamente en el centro cosmico al que llego
* Los centros cosmicos abastecen de energia a la nave y solo pueden abastecer una nave; luego se quedan sin energia.
La tierra va a comprarle a Marte una flota de naves y necesita realizar esta operacion el dia 6 de diciembre. Queremos saber cual es la maxima cantidad de naves que podemos comprar desde la Tierra.

Se podria hacer con flujo maximo asi: Los vertices representan centros cosmicos, los ejes indican si hay camino entre dos centros, y para representar el costo de recarga de energia se pueden dividir los vertices en dos, (ej: A por Ain->Aout) donde el peso del eje tendria el costo.


3) Sea M* un matching maximo de G, y sea M un marching maximal de G. Probar que (donde |M| significa cardinal de M).

|M*| <= #Vertices(M) = 2*|M|

Me parece que M es el cardinal de un matching maximal... Dejo la solución que pensé teniendo en cuenta eso:

Si tenemos un matching maximal M, podemos obtener un recubrimiento de ejes formado por el conjunto de los nodos incidentes a cada eje de M (esto es porque si hubiese un eje no cubierto con este conjunto, no sería "vecino" de ningún eje de M, entonces podríamos agregarlo y no sería maximal). Como pusimos dos nodos por cada eje de M y son disjuntos porque es matching, este recubrimiento de nodos tiene cardinal 2*|M|.
Ahora, si pruebo que |M*| <= |Rn*|, con Rn* el recubrimiento mínimo, ya está, porque va a ser menor a cualquier recubrimiento, en particular al que armamos. Pero esto es lo mismo que probar
n-|Re*| <= n-|I*|, con Re* recubrimiento de nodos mínimo e I* conjunto indep máximo, por las igualdades de la teórica. Y esto es
|I*| <= |Re*| lo cual es cierto por el ejercicio 10.4 de la práctica.



4) Decimos que un grafo es euleriano cuando contiene un circuito euleriano. Sea G un grafo, entonces probar que cada componente conexa es euleriana si y solo si al sacar de G las aristas correspondientes a un circuito de G, el grafo resultante tiene sus componentes conexas eulerianas.

=>) Si cada comp. conexa es euleriana -> al sacar un circuito de G solo se estara modificando dicha comp. conexa, por lo tanto hay que probar que si en un grafo conexo euleriano se saca un circuito (sus ejes) este seguira siendo euleriano.
Esto es cierto ya que cualquiera sea el circuito sacado de G, este debera tener una cantidad par de aristas por vertice que pertenezca a ese circuito (ya que en todo circuito se debe "entrar y salir" una misma cantidad de veces por vertice). Como inicialmente G era euleriano, esto ya tenia una cantidad par de ejes por vertice (siempre me refiero a los grados), y por lo tanto al sacarle una cant. par de ejes a cada vertice del circuito, G sigue teniendo grado par en todos sus vertices, y por lo tanto tambien es euleriano.


<=) La vuelta es casi exactamente igual a la ida, es decir que si agrego un circuito estoy modificando los grados de los vertices sumandoles un numero par, con lo cual todos los vertices de G seguiran teniendo grado par, ya que todas las comp. conexas eran eulerianas y por lo tanto sus vertices tenian grado par.


5) Decidir si son V o F las siguientes afirmaciones. JUSTIFICAR.
(a) Si sabemos que un problema , , entonces
(b) Si un problema es NP-completo, entonces cualquier problema se reduce a
(c) Si son dos problemas NP-completos, entonces se reduce a
(d) Si , es NP-completo, entonces se reduce a .
(e) Si , es NP-completo, entonces se reduce a .
(f) Si , y sabemos que se reduce a , ¿que podemos concluir?
(g) Si , y se reduce a , ¿que podemos concluir?


a) F Si π2 esta en NP -> su solucion se puede verificar en tiempo polinomial en una MTND, lo que no implica que π2 no este en P, es decir que se pueda resolver en tiempo polinomial
b) F Cualquier problema en NP se puede reducir a pero no dice que este en NP.
c) V π1 es NP por ser NP-Completo, y por def. se reduce a cualquier NP-Completo (en particular a π2)
d) V por def. NP-Completo
e) F Si fuera cierto cualquier π en NP se puede reducir a otro NP e inclusive a uno P, con lo cual P=NP (No se sabe)
f) Nada (π1 podria ser igual a π2)
g) π2 es NP-Completo