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.