Parcial del 16/05/15 (Algoritmos III)

De Cuba-Wiki

Plantilla:Back

Ejercicio 1

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

(a) ;

(b) (ciclo simple de vértices);

(c) (camino simple de 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 -ésima instancia cumple a la vez las siguientes tres condiciones:

  • El grafo tiene vértices.
  • La complejidad del algoritmo es si los ejes son analizados en cierto orden.
  • La complejidad del algoritmo es si los ejes son analizados en cierto orden.

Justificar.

Ejercicio 3

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

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

No usar propiedades de caminos ni circuitos eulerianos.

Ejercicio 4

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

Sea un grafo conexo en el cual cada eje tiene asociado un peso no necesariamente positivo . Dada una función , definimos como el grafo que tiene los mismos vértices y ejes que , pero en el cual cada eje tiene asociado el peso en vez de . Sea un árbol generador de , el cual por definición también lo es de , 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 , es un árbol generador mínimo de si y sólo si T es un árbol generador mínimo de ?

(b) para con , es un árbol generador mínimo de si y sólo si T es un árbol generador máximo de ?

(c) para con , es un árbol generador mínimo de si y sólo si T es un árbol generador mínimo de ?

(d) para con , es un árbol generador máximo de si y sólo si T es un árbol generador máximo de ?

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

Ejercicio 5

Diseñar un algoritmo que dado , determine la máxima suma de elementos en posiciones consecutivas de . Ejemplos: para el resultado es 6, para el resultado es 4, para el resultado es 0. El algoritmo debe tener complejidad 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 y espacial (adicional a los datos).

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