Recorridos sobre Grafos

Recorridos sobre Grafos#

Algoritmos: BFS · DFS · Dijkstra#

Pregunta 1 — Ejecución y trazabilidad (BFS)#

BFS

Dado el siguiente grafo no dirigido con vértices {r, s, t, u, v, w, x, y} y listas de adyacencia según la Figura 22.3 del texto:

r — s    r — v    s — w    w — t    w — x
t — u    t — x    x — u    x — y    u — y

  • a) Ejecuta BFS(G, s) paso a paso. Para cada vértice alcanzable indica:

    • El valor de v.d (distancia mínima desde la fuente s)

    • El predecesor v.π

    • El conjunto de tree edges que forman el árbol BFS resultante

  • b) El Teorema 22.5 garantiza que v.d = δ(s, v) al terminar BFS. Explica en qué paso del algoritmo se establece v.d y por qué ese valor ya no cambia.

  • c) ¿Puede el árbol BFS obtenido variar si se reordena la lista de adyacencia de algún vértice? ¿Varían también las distancias d? Justifica apoyándote en el Ejercicio 22.2-5.

Pregunta 2 — Timestamps y clasificación de aristas (DFS)#

DFS

Dado el grafo dirigido con vértices {q, r, s, t, u, v, w, x, y, z}:

  • a) Ejecuta DFS(G) asumiendo orden alfabético tanto en el ciclo principal como en cada lista de adyacencia. Para cada vértice registra los timestamps v.d (descubrimiento) y v.f (finalización).

  • b) Clasifica cada arista del grafo en una de las cuatro categorías definidas por DFS:

Tipo

Condición sobre timestamps

Color del destino al explorar

Tree edge

u.d < v.d < v.f < u.f

WHITE

Back edge

v.d ≤ u.d < u.f ≤ v.f

GRAY

Forward edge

u.d < v.d < v.f < u.f (no tree)

BLACK

Cross edge

v.d < v.f < u.d < u.f

BLACK

c) ¿Qué tipo de arista nunca aparece en un DFS sobre un grafo no dirigido?.

Pregunta 3 — BFS vs. DFS: complejidad y estructura#

  • a) Representación por matriz de adyacencia. Ambos algoritmos tienen complejidad Θ(V + E) sobre listas de adyacencia. ¿Qué sucede con esa complejidad si el grafo se representa con matriz de adyacencia?

    • Demuéstralo para BFS.

    • Argumenta el caso análogo para DFS.

  • b) Árbol vs. Bosque. BFS produce un único árbol BFS desde la fuente s. DFS puede producir un bosque de árboles. ¿A qué se debe esta diferencia estructural? ¿Bajo qué condición sobre el grafo G garantiza DFS producir un único árbol?

  • c) Detección de bipartición. ¿Cuál de los dos algoritmos usarías para determinar si un grafo no dirigido es bipartito? Describe el criterio de clasificación de vértices en dos conjuntos y justifica por qué BFS es la elección natural. Pista: Un grafo es bipartito si y sólo si no contiene ciclos de longitud impar.

Pregunta 4 — De BFS a Dijkstra: caminos mínimos con pesos#

BFS computa distancias mínimas en número de aristas en grafos no ponderados. El algoritmo de Dijkstra generaliza esta idea a grafos con pesos no negativos en las aristas.

  • a) Contraejemplo. Construye un grafo dirigido con 4 vértices y pesos distintos en sus aristas donde BFS devuelva una ruta con menor número de saltos pero mayor costo que la ruta óptima en peso. ¿Cuál es la raíz del problema?

  • b) Invariante de Dijkstra. El algoritmo mantiene un conjunto S de vértices con distancia definitiva y una cola de prioridad mínima Q. Describe el invariante de ciclo que garantiza la corrección y argumenta por qué la condición de pesos no negativos es indispensable. ¿Qué falla exactamente si existe una arista (u, v) con peso negativo?

  • c) Análisis de complejidad. Compara las siguientes variantes y explica en qué escenario (grafo disperso vs. denso) conviene cada una:

Variante

Complejidad

BFS (no ponderado)

O(V + E)

Dijkstra con array simple

O(V²)

Dijkstra con min-heap binario

O((V + E) log V)

Dijkstra con heap de Fibonacci

O(V log V + E)

  • d) Relación con BFS. Explica concretamente qué estructura de datos reemplaza a la cola FIFO de BFS en Dijkstra y cómo ese cambio generaliza el algoritmo de grafos no ponderados a ponderados.

Contents