Estructuras de Datos y de la Información II - Cuestiones y ejercicios

Última modificación: 03/03/10

Cuestión 1

Mostrar un ejemplo pequeño de grafo donde los árboles construidos por BFS y DFS no coinciden.

Cuestión 2

Para cada una de las siguientes situaciones:

  1. v es adyacente a u, y estado[v] = N en el momento de descubrir u.
  2. v es adyacente a u, y estado[v] = N en el momento de visitar u.
  3. v es accesible desde u, y estado[v] = N en el momento de descubrir u.
  4. v es accesible desde u, y estado[v] = N en el momento de visitar u.
Indicar si al final del algoritmo se dará necesariamente o no cada uno de estos dos casos:

  1. π[v] = u.
  2. v desciende de u en el árbol construido por el algoritmo.
Responder a las preguntas para BFS y DFS.
En DFS, responder a las mismas preguntas también para estado[v] = V y estado[v] = P.
Para las respuestas afirmativas razonar la respuesta, y para las negativas mostrar un contraejemplo.
Nota: para BFS, 'descubrir' un nodo significa introducirlo en la cola, y 'visitar' es extraerlo de la cola. En el caso de DFS, descubrir y visitar es lo mismo.

Cuestión 3

  1. ¿El algoritmo de recorrido en anchura BFS cumple el teorema del paréntesis?

  2. ¿El algoritmo de recorrido en anchura BFS cumple el teorema del camino blanco?

  3. Si trasladamos la definición de 'arco hacia atrás' a un árbol construido por BFS:

    1. ¿Puede haber un grafo acíclico sin arcos hacia atrás?
    2. ¿Puede haber un arco hacia atrás en un grafo acíclico?
En todas las preguntas anteriores, en caso de respuesta afirmativa dar una demostración rigurosa, y en otro caso mostrar un contraejemplo.

Cuestión 4

  1. Mostrar un ejemplo donde la solución al problema de los caminos de coste mínimo no coincide con la del árbol abarcador mínimo.

  2. ¿El algoritmo de Prim funciona con grafos dirigidos? En caso afirmativo, dar un argumento riguroso, y en caso contrario mostrar un contraejemplo.