Ejercicios de Recorreguts BFS i DFS

3 ejercicios de Recorreguts BFS i DFS que han salido en los exámenes de Matemática Discreta de la UAB (Grado en Ingeniería Informática) 2026. Con solución.

Pregunta 1 · 2026

Pregunta 1 (5 punts). BFS i detecció de cicles sobre un graf dirigit amb arestes A->B, B->C, B->D, C->A. a) Traça d'execució de les 5 primeres iteracions omplint la taula de variables (actual, visited, to_visit). b) Justificació de per què entra en bucle infinit. c) Indicació de la línia amb error (línia 10) i codi…

Pregunta 2 · 2026

Modelització d'un programa Python i les seves crides com a digraf, selecció de l'estructura de dades (pila) i justificació de la relació amb cerca en profunditat (DFS).

Exercici 5 - Recorreguts BFS i DFS · Juny 2026

Exercici 5, apartat d: Explicar com determinar si encara és possible arribar a totes les poblacions des del magatzem quan algunes carreteres estan tallades, indicant el problema de grafs i l'algorisme emprat.

Otros temas de Matemática Discreta

Combinatòria i relacions

• Combinatòria i recompte · 2 problemas · 35 % de que salga

Grafs, arbres i recorreguts

• Relacions, conceptes bàsics de grafs i seqüències de graus (grafs i arbres) · 5 problemas · 35 % de que salga

Camins, circuits i rutes

• Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra) · 5 problemas · 45 % de que salga
• Grafs eulerians i hamiltonians · 4 problemas · 45 % de que salga
• Optimització de rutes: carter xinès, viatjant de comerç i complexitat · 8 problemas · 45 % de que salga

Planaritat i coloració

• Grafs planars i fórmula d'Euler · 4 problemas · 45 % de que salga
• Coloració de grafs i polinomi cromàtic · 4 problemas · 45 % de que salga