Exámenes de Matemática Discreta UAB 2023
Los 2 exámenes de Matemática Discreta de la UAB (Grado en Ingeniería Informática) de 2023 (Examen Primer Parcial 2023-2024 y Examen Segon Parcial 2023-2024), con 10 problemas resueltos. Entran temas como Combinatòria i recompte y Relacions, conceptes bàsics de grafs i seqüències de graus (grafs i arbres). Practícalos con corrección al momento, pistas en cada apartado y la solución paso a paso.
Examen Primer Parcial 2023-2024 (2023)
Temas del examen: Combinatòria i recompte · Relacions, conceptes bàsics de grafs i seqüències de graus (grafs i arbres) · Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra)
- Exercici 1 · Combinatòria i recompte
A la vila universitària cal allotjar 9 estudiants entre tres habitacions retolades (1, 2 i 3). a) De quantes maneres si no hi ha restriccions? b) De quantes formes si a l'habitació 1 en van 4, a la 2… - Exercici 2 · Relacions, conceptes bàsics de grafs i seqüències de graus (grafs i arbres)
Determineu el nombre d'arbres no isomorfs d'ordre 16 que compleixen que tots els seus vèrtexs tenen grau g1 > 3 o bé g2 = 1. Indiqueu quants vèrtexs hi ha de grau g1 en cada cas. - Exercici 3 · Relacions, conceptes bàsics de grafs i seqüències de graus (grafs i arbres)
Quantes seqüències no ordenades de xifres del tipus x, x, x, y, y, y, 3 (amb x > 3, x > y i y parell) hi ha que siguin la seqüència de graus d'un graf connex? - Exercici 4 · Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra)
Preguntes teòriques sobre l'algorisme de Floyd-Warshall per a camins mínims entre tots els parells de vèrtexs i detecció de cicles de cost negatiu. - Exercici 5 · Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra)
En relació amb els algorismes clàssics d'optimització sobre grafs: a. Diferencieu el problema del camí mínim d'origen únic (Dijkstra) del problema de l'arbre d'extensió mínim (Kruskal o Prim). b.…
Examen Segon Parcial 2023-2024 (2023)
Temas del examen: 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
- Pregunta 1 · Grafs planars i fórmula d'Euler
Considerem un políedre convex format per 24 vèrtexs i 36 arestes, amb cares acotades només per 6 o 4 arestes. a) Quin és el nombre total de cares? b) Quantes d'aquestes cares tenen 6 arestes i… - Pregunta 2 · Coloració de grafs i polinomi cromàtic
a) Donat el polinomi cromàtic f(G,t) = t^9 - 6t^8 + 14t^7 - 16t^6 + at^5 - bt^4: 1. Determineu |V|, |E| i components connexos. 2. Trobeu a i b si χ(G) > 2. b) Calculeu el polinomi cromàtic i deduïu… - Pregunta 3 · Grafs eulerians i hamiltonians
Pregunta 3: Propietats eulerianes i hamiltonianes en grafs bipartits complets i aplicació del teorema de Grinberg en un graf pla. - Pregunta 4 · Optimització de rutes: carter xinès, viatjant de comerç i complexitat
Aplicar l'algorisme d'aproximació de Christofides sobre el graf complet K6 donat per la seva matriu de pesos per obtenir un cicle hamiltonià amb c(H) <= 3/2 c(H_0). - Pregunta 5 · Optimització de rutes: carter xinès, viatjant de comerç i complexitat
Pregunta 5: Anàlisi de cert o fals de 4 afirmacions sobre reduccions en temps polinòmic, NP, NP-hard i NP-complet.
También puedes estudiar por temas
Practica un tema con ejercicios de los exámenes de todos los años, mezclados.
- 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
- Relacions, conceptes bàsics de grafs i seqüències de graus (grafs i arbres) · 5 problemas · 35 % de que salga