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.

Ejercicio 4

(a) Sea $G=(V_{G},E_{G})$ un grafo no trivial. Demostrar que $G$ es bipartito sí y solo sí existe $I\subseteq V_{G}$ tal que $I$ 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 $G=(V_{G},E_{G})$, encuentre un conjunto independiente mínimo de $G$ 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 $O(m+n)$, donde $m=|E_{G}|$ y $n=|V_{G}|$.

Ejercicio 5

El problema del conjunto dominante es: dado un grafo $G=(V_{G},E_{G})$ y un entero $k$, ¿existen un subconjunto $W\subseteq V_{G}$ con a lo sumo $k$ vértices tal que cualquier vértice $u\in V_{G}\ W$, $u$ es vecino de algún vértice $w\in W$? 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).