Ejercicios de Optimització de rutes: carter xinès, viatjant de comerç i complexitat
8 ejercicios de Optimització de rutes: carter xinès, viatjant de comerç i complexitat que han salido en los exámenes de Matemática Discreta de la UAB…
Exercici 4 · Juny 2026
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 circuit tancat que comença a A, les arestes duplicades i el cost total mínim.
Exercici 5 - Viatjant de comerç · Juny 2026
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 condicions d'una ruta vàlida.
Pregunta 3 (apartat d) - Problema del carter xinès · 2024
Assumint que totes les arestes tenen cost unitari (pes = 1), determineu el cost mínim d'un recorregut tancat que passi com a mínim una vegada per cada aresta (problema del carter xinès), indicant quines arestes cal duplicar i un possible circuit resultant.
Pregunta 4 · 2024
Aplicació pas a pas de l'algorisme de Christofides (AGM amb Kruskal, identificació de vèrtexs de grau imparell, aparellament perfecte de cost mínim, circuit eulerià amb dreceres hamiltonianes i verificació de la cota d'aproximació) sobre un graf complet K7 donat per una matriu de pesos.
Pregunta 4 · 2023
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 · 2023
Pregunta 5: Anàlisi de cert o fals de 4 afirmacions sobre reduccions en temps polinòmic, NP, NP-hard i NP-complet.
Ejercicio 4 · Juny 2022
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 coste(H_0).
Ejercicio 5 · Juny 2022
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. Si A es NP-hard, B es NP-completo. c. Si A ∈ NP, es posible que B sea resoluble en tiempo polinómico. d. Si B es…
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
- Recorreguts BFS i DFS · 3 problemas · 50 % 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
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