Abrir menú principal

Cuba-Wiki β

Final del 30/07/15 (Algoritmos III)

Ejercicio 1Editar

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 2Editar

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 3Editar

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 4Editar

(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 5Editar

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.