Final del 20/12/19 (Algoritmos III)

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 $O(n.log(n))$ y usa espacio $O(n)$). Mostrar la correctitud y determinar la complejidad del algoritmo propuesto.

Ejercicio 2

El grafo $Q_{d}$, también llamado hipercubo de orden $d$, se define inductivamente de la siguiente manera: $Q_{0}=K_{1}$, y $Q_{d}$ con $d\in N_{>}0$ es el grafo que se obtiene al tomar dos copias de $Q_{d}-1$ y agrega un eje entre cada vértice de una copia y su vértice correspondiente en la otra copia. Por ejemplo $Q_{1}=K_{2}$, $Q_{2}=C_{4}$ (ciclo simple de 4 vértices).

(a) Determinar los valores de $d$ para los cuales $Q_{d}$ es planar. Justificar.

(b) Determinar $\chi (Q_{d})$. Justificar.

Ejercicio 3

Dado un grafo $G=(V_{G},E_{G})$, se define la excentricidad de un vértice $v\in V_{G}$ como $e_{G}(v)=max\{dist_{G}(v,w)/\forall w\in V_{G}\}$ y $dist_{G}(v,w)$ como la cantidad de aristas del camino más corto entre $v$ y $w$. Y también se definen el radio y el diámetro de $G$ como $r(G)=min\{e_{G}(v)/\forall v\in V_{G}\}$ y $d_{G}=max\{e_{G}(v)/\forall v\in V_{G}\}$. Un vértice $v\in E_{G}$ es centro de $G$ si $e_{G}(v)=r(G)$.

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