Ejercicios resueltos de algoritmos de búsqueda

Lista de adyacencia:

• $1$: [2, 3]
• $2$: [1, 4]
• $3$: [1, 5]
• $4$: [2, 6]
• $5$: [3, 6]
• $6$: [4, 5]

Orden BFS: 1 → 2 → 3 → 4 → 5 → 6

Asumiendo orden lexicográfico en listas de adyacencia:

Orden DFS: 1 → 2 → 4 → 6 → 5 → 3

BFS (por niveles):

• Nivel 0: {1}
• Nivel 1: {2, 3}
• Nivel 2: {4, 5}
• Nivel 3: {6}

DFS (en profundidad): Explora un camino completamente antes de retroceder

Distancias desde vértice 1: d(1)=0, d(2)=1, d(3)=1, d(4)=2, d(5)=2, d(6)=3

Inicializar todos los vértices como no visitados.

DFS desde A:

• Visita A → B → C
• Componente 1: {A, B, C}

DFS desde D (primer no visitado):

• Visita D → E
• Componente 2: {D, E}

DFS desde F (primer no visitado):

• Visita F → G → H
• Componente 3: {F, G, H}

El grafo $H$ tiene 3 componentes conexas:

1. Componente 1: {A, B, C}
2. Componente 2: {D, E}
3. Componente 3: {F, G, H}

Componente 1: {A, B, C} con aristas {AB, BC}

• Árbol de expansión: A—B—C
• Aristas del árbol: {AB, BC}

Componente 2: {D, E} con arista {DE}

• Árbol de expansión: D—E
• Aristas del árbol: {DE}

Componente 3: {F, G, H} con aristas {FG, FH, GH}

• Es un ciclo, necesitamos eliminar una arista
• Árbol de expansión posible: F—G—H
• Aristas del árbol: {FG, GH} (eliminamos FH)

Para cada árbol con $n$ vértices, debe tener exactamente $n-1$ aristas:

• Componente 1: 3 vértices, 2 aristas $\checkmark$
• Componente 2: 2 vértices, 1 arista $\checkmark$
• Componente 3: 3 vértices, 2 aristas $\checkmark$

Estados de vértices:

• Blanco: No visitado
• Gris: En proceso (en el stack de recursión)
• Negro: Completamente procesado

Regla: Si durante DFS encontramos una arista hacia un vértice gris, hay un ciclo.

Lista de adyacencia:

• 1: [2, 5]
• 2: [3]
• 3: [4]
• 4: [2]
• 5: [4]

Ejecutar DFS desde vértice 1:

Ciclo detectado: La arista (4,2) es una back edge porque conecta el vértice 4 (actual) con el vértice 2 (antepasado en el árbol DFS).

Ciclo encontrado: 2 → 3 → 4 → 2

• (1,2): Tree edge
• (2,3): Tree edge
• (3,4): Tree edge
• (4,2): Back edge (indica ciclo)
• (1,5): Tree edge
• (5,4): Cross edge

Conclusión: El grafo dirigido contiene un ciclo.

Un puente es una arista cuya eliminación aumenta el número de componentes conexas.

Conceptos clave:

• $disc[v]$: tiempo de descubrimiento del vértice $v$
• $low[v]$: menor tiempo de descubrimiento alcanzable desde $v$
• Una arista $(u,v)$ es puente si $low[v] > disc[u]$

Lista de adyacencia:

• a: [b]
• b: [a, c, e]
• c: [b, d, f]
• d: [c, e]
• e: [d, f, b]
• f: [e, c]

Para cada arista $(u,v)$ en el árbol DFS:

• (a,b): $low[b] = 1 > disc[a] = 0$ → Puente
• (b,c): $low[c] = 1 \not> disc[b] = 1$ → No es puente
• (c,d): $low[d] = 1 \not> disc[c] = 2$ → No es puente
• (d,e): $low[e] = 1 \not> disc[d] = 3$ → No es puente
• (e,f): $low[f] = 2 \not> disc[e] = 4$ → No es puente

Aristas back:

• (e,b): No es puente (crea ciclo)
• (f,c): No es puente (crea ciclo)

Puentes encontrados: $\{(a,b)\}$

Verificación:

• Eliminar (a,b): separa {a} de {b,c,d,e,f}
• Eliminar (b,c): no desconecta, porque queda el camino b–e–d–c
• Eliminar (c,d): no desconecta, porque queda el camino c–f–e–d

Solo la eliminación de (a,b) aumenta las componentes conexas de 1 a 2.