Final del 20/12/19 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar

Final escrito de Min Chih Lin.

Enunciados

Ejercicio 1

Escribir un algoritmo que utilice la técnica de "programación dinámica" para calcular la subsecuencia creciente máxima de una secuencia de números (el mejor algoritmo conocido es de tiempo y usa espacio ). Mostrar la correctitud y determinar la complejidad del algoritmo propuesto.


Ejercicio 2

El grafo , también llamado hipercubo de orden , se define inductivamente de la siguiente manera: , y con es el grafo que se obtiene al tomar dos copias de y agrega un eje entre cada vértice de una copia y su vértice correspondiente en la otra copia. Por ejemplo , (ciclo simple de 4 vértices).

(a) Determinar los valores de para los cuales es planar. Justificar.

(b) Determinar . Justificar.


Ejercicio 3

Dado un grafo , se define la excentricidad de un vértice como y como la cantidad de aristas del camino más corto entre y . Y también se definen el radio y el diámetro de como y . Un vértice es centro de si .

(a) Mostrar infinitos grafos conexos (distintos de completos y ciclos) donde todos los vértices son centros.

(b) Probar que todo árbol tiene uno o dos centros.

(c) Escribir un algoritmo eficiente basado en el resultado anterior que determine el radio y el diámetro de un árbol T. Mostrar la correctitud y determinar la complejidad del algoritmo propuesto.


Ejercicio 4

(a) Sea un grafo no trivial. Demostrar que es bipartito sí y solo sí existe tal que es un conjunto independiente y también un recubrimiento de ejes por vértices (vertex cover).

(b) Diseñar un algoritmo eficiente que dado un grafo , encuentre un conjunto independiente mínimo de que sea también un recubrimiento de ejes por vértices; si tal conjunto de vértices no existe, el algoritmo debe informarlo. Mostrar que algoritmo propuesto es correcto y determinar su complejidad. Justificar. El mejor algoritmo que conocemos tiene complejidad , donde y .


Ejercicio 5

El problema del conjunto dominante es: dado un grafo y un entero , ¿existen un subconjunto con a lo sumo vértices tal que cualquier vértice , es vecino de algún vértice ? Este problema es NP-Completo para la clase general de grafos. Probar que este problema sigue siendo NP-Completo para grafos bipartitos. (sugenerencia: utilizar subdivisiones de aristas que es agregar vértices de grado 2).