Final del 30/07/15 (Algoritmos III)

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

Ejercicio 1

Dado un subconjunto y un entero , diseñar un algoritmo que devuelva si existe un subconjunto de tal que su suma sea igual a . El algoritmo debe estar basado en programación dinámica. Mostrar que el algoritmo es correcto y demostrar su complejidad.

Ejercicio 2

Decidir si las siguientes afirmaciones son verdaderas o falsas. Justificar.

  • conexo, tiene un único arbol generador si y sólo si es un árbol.
  • tiene un único árbol generador de peso mínimo, entonces es un árbol.
  • Un eje de está en todo árbol generador si y sólo si es un puente.
  • es un eje que está en un árbol generador mínima si y sólo si está en un circuito simple en el cual tiene peso mínimo.

Ejercicio 3

El algoritmo de Dijkstra calcula el camino mínimo entre dos vértices en un grafo con peso en los ejes no negativo. Tenemos un grafo en el cual los vértices también tienen un peso no negativo, el cual se agrega al peso total del camino. Modificar el algoritmo de Dijkstra para poder calcular el camino mínimo en este nuevo grafo. Demostrar que el algoritmo propuesto es correcto.

Ejercicio 4

(a) ¿Puede ser que un grafo y su complemento sean ambos planares? Justificar.

(b) ¿Es cierto que un grafo es planar si y sólo si todos sus subgrafos propios son planares? Justificar.

Ejercicio 5

El problema decide si dado un conjunto y , existe un subconjunto de tal que su suma sea igual a . Este problema es NP-completo. El problema decide si dado un conjunto , existe una partición en dos subconjuntos tales que la diferencia entre las sumas de los subconjuntos sea menor o igual a . Demostrar que este problema es NP-completo, utilizando que es NP-completo.