Parcial del 16/05/15 (Algoritmos III)

Ejercicio 1

Determinar los valores de $n$ para los cuales los siguientes grafos son bipartitos. Justificar.

(a) $K_{n}$;

(b) $C_{n}$ (ciclo simple de $n\geq 3$ vértices);

(c) $P_{n}$ (camino simple de $n$ vértices).

Ejercicio 2

En cada iteración del algoritmo de Ford se analizan todos los ejes de un grafo intentando mejorar los caminos desde cierto vértice origen hacia cada uno de los vértices del grafo. Considerar la versión del algoritmo que termina cuando no hay ninguna mejora durante una iteración completa. Exhibir una familia infinita de instancias tal que la $n$-ésima instancia cumple a la vez las siguientes tres condiciones:

• El grafo tiene $n$ vértices.
• La complejidad del algoritmo es $O(n)$ si los ejes son analizados en cierto orden.
• La complejidad del algoritmo es $\Omega (n^{2})$ si los ejes son analizados en cierto orden.

Justificar.

Ejercicio 3

Un bosque de grado acotado por $d$ es un grafo sin ciclos en el cual todos los vértices tienen grado a lo sumo $d$. Un grafo se dice $d$-regular si y sólo si todos sus vértices tienen grado $d$.

(a) Demostrar que un grafo es un bosque de grado acotado por 2 si y sólo si cada una de sus componentes conexas es un camino simple.

(b) Demostrar que un grafo es 2-regular si y sólo si cada una de sus componentes conexas es un circuito simple.

(c) Demostrar que un grafo es 1-regular si y sólo si cada una de sus componentes conexas es $K_{2}$.

No usar propiedades de caminos ni circuitos eulerianos.

Ejercicio 4

Dado un grafo conexo $G$ con pesos asociados a sus ejes, un árbol generador máximo de $G$ es un árbol generador de $G$ que tiene peso máximo entre todos los árboles generadores de $G$.

Sea $G$ un grafo conexo en el cual cada eje $e$ tiene asociado un peso no necesariamente positivo $p(e)\in \mathbb {R}$. Dada una función $f:\mathbb {R} /rightarrow\mathbb {R}$, definimos $G_{f}$ como el grafo que tiene los mismos vértices y ejes que $G$, pero en el cual cada eje $e$ tiene asociado el peso $f(p(e))$ en vez de $p(e)$. Sea $T$ un árbol generador de $G$, el cual por definición también lo es de $G_{f}$, y cuyo peso total en cada grafo es la suma de los pesos asociados a sus ejes en ese grafo. ¿Es cierto que...

(a) para $f(x)=x+b$, $T$ es un árbol generador mínimo de $G$ si y sólo si T es un árbol generador mínimo de $G_{f}$?

(b) para $f(x)=a\times x$ con $a<0$, $T$ es un árbol generador mínimo de $G$ si y sólo si T es un árbol generador máximo de $G_{f}$?

(c) para $f(x)=a\times x$ con $a>0$, $T$ es un árbol generador mínimo de $G$ si y sólo si T es un árbol generador mínimo de $G_{f}$?

(d) para $f(x)=a\times x$ con $a>0$, $T$ es un árbol generador máximo de $G$ si y sólo si T es un árbol generador máximo de $G_{f}$?

En caso afirmativo demostrar; en caso negativo dar un contraejemplo y justificar.

Ejercicio 5

Diseñar un algoritmo que dado $v\in \mathbb {R} ^{n}$, determine la máxima suma de elementos en posiciones consecutivas de $v$. Ejemplos: para $v=(1,-1,1,2,-1,4,-1)$ el resultado es 6, para $v=(1,-1,1,2,-5,4,-1)$ el resultado es 4, para $v=(-1)$ el resultado es 0. El algoritmo debe tener complejidad $O(n)$ y estar basado en programación dinámica. Mostrar que el algoritmo propuesto es correcto y determinar su complejidad (temporal y espacial). Justificar. El mejor algoritmo que conocemos tiene complejidad temporal $O(n)$ y espacial $O(1)$ (adicional a los datos).

SUGERENCIA: Calcular para cada posición del vector la máxima suma que termina en esa posición.