Exámenes de Matemática Discreta UAB 2026
Los 2 exámenes de Matemática Discreta de la UAB (Grado en Ingeniería Informática) de 2026 (Juny y Examen de seminaris Parcial 1 (20/04/2026)), con 9 problemas resueltos. Entran temas como Recorreguts BFS i DFS y Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra). Practícalos con corrección al momento, pistas en cada apartado y la solución paso a paso.
Juny (2026)
Temas del examen: Recorreguts BFS i DFS · Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra) · Grafs eulerians i hamiltonians · Optimització de rutes: carter xinès, viatjant de comerç i complexitat · Grafs planars i fórmula d'Euler · Coloració de grafs i polinomi cromàtic
- Exercici 1 · Grafs planars i fórmula d'Euler
Considerem un poliedre convex format per 60 vèrtexs on totes les cares són triangles, quadrilàters o pentàgons, cada vèrtex té grau 4 i hi ha 20 triangles. Calculeu: a) el nombre total d'arestes, b)… - Exercici 2 · Coloració de grafs i polinomi cromàtic
Exercici 2. a. Sigui G = T ∪ K_5 ∪ {v_1, v_2} on T té 6 vèrtexs. 1) Polinomi cromàtic de T i de K_5. 2) Polinomi cromàtic de G. 3) Nombre cromàtic de G. 4) Maneres d'acolorir G amb χ(G) colors. b.… - Exercici 3 · Grafs eulerians i hamiltonians
Exercici 3 (2 punts). Grafs eulerians i hamiltonians: a) Determinar si G1 és eulerià i si té camí eulerià. b) Demostrar que el complementari d'un graf d-regular d'ordre n >= 2d + 2 és hamiltonià. c)… - Exercici 4 · Optimització de rutes: carter xinès, viatjant de comerç i complexitat
Resolució completa del problema del carter xinès sobre una xarxa viària ponderada amb 10 vèrtexs. Es demana identificar el problema clàssic i l'algorisme emprat, i mostrar els passos per trobar el… - Exercici 5 - Viatjant de comerç · Optimització de rutes: carter xinès, viatjant de comerç i complexitat
Exercici 5, apartats a i b: Explicar com es modelitza la situació mitjançant un graf ponderat (què són vèrtexs, arestes i pesos) i quin problema clàssic d'optimització representa, indicant les… - Exercici 5 - Arbre generador de cost mínim · Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra)
Exercici 5, apartat c: Indicar quin problema de teoria de grafs modelitza connectar totes les poblacions amb cost total mínim i anomenar un algorisme per resoldre'l. - Exercici 5 - Recorreguts BFS i DFS · Recorreguts BFS i DFS
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…
Examen de seminaris Parcial 1 (20/04/2026) (2026)
Temas del examen: Recorreguts BFS i DFS
- Pregunta 1 · Recorreguts BFS i DFS
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,… - Pregunta 2 · Recorreguts BFS i DFS
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).
También puedes estudiar por temas
Practica un tema con ejercicios de los exámenes de todos los años, mezclados.
- Recorreguts BFS i DFS · 3 problemas · 50 % de que salga
- Optimització de rutes: carter xinès, viatjant de comerç i complexitat · 8 problemas · 45 % de que salga
- 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
- 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