Segundo Parcial 14/07/2004 (Algoritmos III)

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


1) Sea G = (n 2) un grafo completo no dirigido con pesos arbitrarios asociados a sus ejes. Sea (G) cualquier eje de G que tenga peso minimo y (G) cualquier eje de G que tenga peso maximo, ¿Es cierto que...
(a) (G) pertenece a algun camino hamiltoniano de peso minimo de G?
(b) (G) pertenece a todo camino hamiltoniano de peso minimo de G?
(c) (G) no pertenece a algun camino hamiltoniano de peso minimo de G?
(d) (G) no pertenece a ningun camino hamiltoniano de peso minimo de G?
Repetir suponiendo que los pesos cumplen la desigualdad triangular. En todos los casos justificar la respuesta

a) Sup. que hay un camino hamiltoniano tq todos los ejes valen 1, hay un eje que vale 0 que conecta con 2 vertices del camino, y los del resto del grafo valen 1000. Entonces si se quiere pasar por el minimo (en este caso 0), necesariamente hay que pasar por un eje que vale 1000, con lo cual ya no seria de peso minimo
b) Idem a)
c) F Sup. que tenemos un K2. Entonces hay un unico camino hamiltoniano, y el peso del unico eje es a la vez minimo y maximo
d) Idem c)


2) Sea G un grafo planar, no necesariamente conexo. ¿Es cierto que cualquier representacion planar de G tiene la misma cantidad de regiones?. Justificar.

Por teorema de Euler n-m+r=2 -> r=2-n+m, con lo cual depende de la cantidad de vertices y ejes, y esto no se modifica en ninguna representacion planar -> Por lo tanto siempre se tiene la misma cantidad de regiones


3) Encontrar una familia infinita de grafos tales que el n-esimo grafo tenga n vertices y conjuntos independientes maximales. Justificar. SUGERENCIA: Dividir los nodos en grupos de 3 y agregar ejes de tal modo que en cada grupo haya 3 opciones diferentes.

Si se van formando K3 con grupos de 3 y se dejan los demas vertices aislados sale


4) Al casamiento de Fausto y Filomena concurren p familias. Sea el numero de miembros de la i-esima familia (i = 1,2,..,p). Por otra parte, se dispone de q mesas donde ubicar a los concurrentes. Sea la cantidad de personas que caben en la j-esima mesa (j = 1,2,..,q). Fausto y Filomena desean que en ninguna mesa haya dos personas en la misma familia. Dise~nar un algoritmo eficiente para ubicar a los concurrentes en las mesas de manera tal que se cumpla esa regla. Mostrar la correctitud y determinar la complejidad del algoritmo propuesto. Justificar.

Este sale con flujo maximo asi: De s salen ejes a las p familias (cada uno con su correspondiente ai), luego se forma un bipartito completo con las q mesas (donde todos los ejes tienen capacidad 1), y finalmente de las mesas se va a t (cada una con su correspondiente bj)


5) Dados los problemas y encontrar una reduccion polinomial de a y otra de a . Demostrar que efectivamente son reducciones polinomiales.

: Entrada: un conjunto A de enteros positivos.
Pregunta: ¿existe A' A tal que suma(A') = suma(A - A')?
: Entrada: un conjunto A de enteros.
Pregunta: ¿existe A' A tal que suma(A') = suma(A - A')?


Hay que probar el <=>
2->1) Si se puede resolver para enteros, en particular tambien para enteros positivos
1->2)
1. Aca lo que se puede hacer es "convertirlos" en positivos, es decir, tomar el minimo numero negativo (si hay), tomarle el valor abs. y sumarselo a todos los enteros del conjunto (si suma(A)=suma(B) -> suma(A)+cte = suma(B)+cte)
2. Me pa que el 1->2 es distinto. la idea mas facil de ver para mi al menos es: suma(A') = suma(A-A').Pasamos los numeros negativos a positivos.
Sea x = La suma de todos los numeros originalmente positivos en suma(A')
Sea y = La suma de todos los numeros originalmente positivos en suma(A-A')
Sea u = La suma de los numeros originalmente negativos (convertidos a positivos) de suma(A')
Sea v = La suma de los numeros originalmente negativos (convertidos a positivos)de suma(A-A')
Luego segun nuestra version para enteros positivos tenemos que x + u = y + v
Entonces tenemos que x - v = y - u.
Es decir, si cambiamos de lugar los originalmente negativos de un conjunto a otro, entonces la igualdad sigue valiendo.
Si no se entiende, posteen algo ak diciendo no entendi y lo intento hacer mas entendible.
NO ENTENDI.. Y HACE 1 MES QUE ESPERO LA EXPLICACION