Parcial del 04/07/15 (Algoritmos III)

Ejercicio 1

Dada una representación planar de un grafo planar $G$, se define a su (pseudo-multi) grafo dual $G^{*}$ de la siguiente manera: por cada región de la representación planar de $G$ se agrega un vértice en $G^{*}$; por cada eje de la representación planar de $G$ se agrega un eje en $G^{*}$ entre los vértices correspondientes a las regiones que están a ambos lados de $e$ en $G$. Un grafo planar $G$ se dice autodual si es isomorfo a su dual.

Exhibir todos los árboles no isomorfos autoduales. Justificar.

Ejercicio 2

Sea $G$ un grafo de $m$ ejes.

(a) Demostrar que $2m\geq (k-1)k$, donde $k$ es la cantidad de vértices de un subgrafo completo máximo de $G$.

(b) Demostrar que $2m\geq (k-1)k$, donde $k$ es $\chi (G)$.

Ejercicio 3

Supongamos que se dispone de un algoritmo que dado un grafo y un entero $k$, informa en tiempo polinomial si el grafo tiene un conjunto independiente formado por $k$ o más vértices. En base a ese algoritmos, diseñar un nuevo algoritmo que dado un grafo $G$ de $n$ vértices, encuentre en tiempo polinomial un conjunto independiente máximo de $G$. El algoritmo propuesto deve invocar al algoritmo original $O(n)$ veces. Mostrar que el algoritmo propuesto es correcto y determinar la cantidad de veces que invoca al algoritmo original. Justificar. La cantidad de veces que el mejor algoritmo que conocemos invoca al algoritmo original es $n+\log _{2}n+O(1)$, lo cual es necesario para obtener puntaje máximo en este ejercicio.

Ejercicio 4

Demostrar detalladamente que alguno de los siguientes problemas es NP-completo usando que el otro lo es. Indicar claramente cuál problema se intenta demostrar que es NP-completo y cuál se supone que lo es.

$\Pi _{1}$: CAMINO HAMILTONIANO

Entrada: grafo $G$

Pregunta: ¿existe un camino que pasa exactamente una vez por cada vértices de $G$?

$\Pi _{2}$: CAMINO MÁXIMO

Entrada: grafo $G$ de $n$ vértices; $k\in \mathbb {Z}$ tal que $0\leq k\leq n-1$.

Pregunta: ¿tiene $G$ un camino simple de $k$ o más ejes?

Ejercicio 5

Sea $G$ un grafo. Demostrar que son equivalentes:

(a) $G$ tiene ejes, y es arbitrariamente atravesable desde todos sus vértices.

(b) $G$ no tiene vértices aislados, y es arbitrariamente atravesable desde al menos tres vértices distintos.

(c) $G$ tiene circuitos simples, y todos ellos son hamiltonianos.

(d) $G$ es $C_{n}$ (ciclo simple de $n\geq 3$ vértices).

SUGERENCIA: Salen $(5b)\Rightarrow (5c)$ y $(5b)\Rightarrow (5d)$, entre otras.