Abrir menú principal

Cuba-Wiki β

Final del 20/12/19 (Algoritmos III)

Final escrito de Min Chih Lin.

Sumario

EnunciadosEditar

Ejercicio 1Editar

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

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

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

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

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).