Segundo Parcial 10/12/2003 (Algoritmos III)

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


1) Un grafo G se llama domino si cada vertice de G pertenece exactamente a dos cliques distintas. Reducir el problema de hallar un conjunto independiente maximo de un grafo domino al problema de hallar un matching de un grafo. Que pued edecir de la complejidad del problema?


2) demostrar que dado un grafo G, X(G) <= 1 + maxdelta(G') donde el maximo es tomado sobre todo G' subgrafo inducido de G. Ayuda: Recordar que todo grafo k-cromatico tiene un sibgrafo inducido k-cromatico y color critico y utilizar las propiedades de los grafos color criticos.


3) Supongamos que en una ciudad hay m edicios donde viven a1,a2,...,am personas respectivamente, y n refugios subterraneos con capacidades b1,b2,...,bn respectivamente, con a1+...+am <= b1+...+bn. Dadas las coordenadas de los edificios y de los refugios, se quiere dise;ar un plan de evacuacion optimo,es decir, distribuir la gente de los edificios en los refugios de manera tal que la distancia total recorrida (la suma de las distancias recorridas por cada habitante de la ciudad) sea minima. Modelar como el problema de flijo.


4) Demostrar que si el grafo G=(V,E) es hamiltonia y W es un subconjunto propio de V,no vacio, el subgrafo de G inducido por V-W tiene a lo sumo |W| componentes conexas. Vale la reciproca?


5) Considerar la modificacion del problema de maximo flujo. Llamamos a un flujo saturado si cumple las restricciones usuales de flujo y ademas todo arco tiene flujo cero o esta completamente saturado. En otras palabras, si existe flujo a trves de un arco, ese flujo es igual a la capacidad del arco. El nuevo problema consiste en encontrar el maximo flujo saturado.
a) Formular este problema como un problema de desicion (lo llamaremos MAX-SATURATED-FLOW)
b) Demostrar que MAX-SATURATED-FLOW es NP-Completo, usando el hecho de que encontra run subconjunto de {s1,...,sn} numero enteros positivos que sumen t es NP-Completo.