Exámenes de Matemática Discreta UAB 2022
El examen de Matemática Discreta de la UAB (Grado en Ingeniería Informática) de 2022 (Juny), con 5 problemas resueltos. Entran temas como Grafs eulerians i hamiltonians y Optimització de rutes: carter xinès, viatjant de comerç i complexitat. Practícalos con corrección al momento, pistas en cada apartado y la solución paso a paso.
Juny (2022)
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
- Ejercicio 1 · Grafs planars i fórmula d'Euler
Consideremos un poliedro convexo con 12 vértices y 24 aristas cuyas caras están delimitadas por j o por 4 aristas. Determina el número total de caras C, el valor entero de j, y el número de caras de… - Ejercicio 2 · Coloració de grafs i polinomi cromàtic
Dado f(G,t) = t^5 - 3t^4 - at^3 + t^2, determina el número de vértices, componentes conexas, la constante a y el número cromático de G. Además, deduce el polinomio cromático de un bosque de orden n… - Ejercicio 3 · Grafs eulerians i hamiltonians
a. Justifica que si K_{m,n} es euleriano, su número de aristas es múltiplo de 4. b. Usando el teorema de Grinberg, justifica si puede ser hamiltoniano un grafo plano con 7 caras interiores de 3… - Ejercicio 4 · Optimització de rutes: carter xinès, viatjant de comerç i complexitat
Aplicación del algoritmo de Christofides para el TSP a un grafo ponderado K_6 dados sus pesos en una tabla de distancias. Determinar un ciclo hamiltoniano H con su coste y calcular las cotas de… - Ejercicio 5 · Optimització de rutes: carter xinès, viatjant de comerç i complexitat
Supongamos que un problema A se puede reducir en tiempo polinómico a un problema B (A ≤_p B). Justifica razonadamente la veracidad o falsedad de: a. Si A es ciclo hamiltoniano, B es NP-completo. b.…
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 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
- Recorreguts BFS i DFS · 3 problemas · 50 % de que salga
- Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra) · 5 problemas · 45 % de que salga