Final del 30/07/15 (Algoritmos III)

Ejercicio 1

Dado un subconjunto $S=\{s_{1},s_{2}\dots s_{n}\}$ y un entero $k$, diseñar un algoritmo que devuelva si existe un subconjunto de $S$ tal que su suma sea igual a $k$. 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.

• $G$ conexo, $G$ tiene un único arbol generador si y sólo si $G$ es un árbol.
• $G$ tiene un único árbol generador de peso mínimo, entonces $G$ es un árbol.
• Un eje $e$ de $G$ está en todo árbol generador si y sólo si $e$ es un puente.
• $G$ es un eje que está en un árbol generador mínima si y sólo si $e$ 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 $G$ y su complemento ${\overline {G}}$ sean ambos planares? Justificar.

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

Ejercicio 5

El problema $SubsetSum$ decide si dado un conjunto $S=\{s_{1},s_{2}\dots s_{n}\}$ y $k\in \mathbb {N} _{0}$, existe un subconjunto de $S$ tal que su suma sea igual a $k$. Este problema es NP-completo. El problema $Partition$ decide si dado un conjunto $S=\{s_{1},s_{2}\dots s_{n}\}$, existe una partición en dos subconjuntos tales que la diferencia entre las sumas de los subconjuntos sea menor o igual a $k$. Demostrar que este problema es NP-completo, utilizando que $SubsetSum$ es NP-completo.