Exercici 4 · Matemática Discreta UAB Juny 2026
Tema: Optimització de rutes: carter xinès, viatjant de comerç i complexitat · Del examen Juny (2026)
Enunciado
Exercici 4 (2,5 punts). Problema del carter xinès
Un servei municipal ha de recórrer tots els carrers d'un barri per fer una inspecció i tornar al punt d'inici. El barri es representa mitjançant el següent graf ponderat, on els pesos indiquen la longitud dels carrers en minuts:
Partint del vèrtex A, trobeu el circuit tancat de cost mínim que passa com a mínim una vegada per cada aresta del graf.
a)
[0,5 punts] Indiqueu a quin problema clàssic correspon i el nom de l'algorisme o mètode vist a classe que el resol.
b)
[2 punts] Mostreu detalladament tots els passos de l'algorisme. Indiqueu finalment:
Solución
Según los criterios oficiales de corrección
a) Indiqueu a quin problema clàssic correspon
Solución: Problema del carter xinès (Chinese Postman Problem)
a) Indiqueu el nom de l'algorisme o mètode vist a classe que el resol
Solución: Algorisme d'Edmonds-Johnson / Algorisme de Hierholzer / Fleury
b.1. El circuit tancat obtingut
Solución: A -> E -> P -> G -> B -> G -> J -> D -> J -> E -> H -> G -> J -> U -> H -> C -> H -> E -> A
b.2. Quins carrers cal recórrer més d'una vegada (duplicats)
Solución: AE, EH, HC, BG, GJ, JD
b.3. El cost total mínim del recorregut
Solución: 55 minuts
La explicación paso a paso, hecha con IA, es Premium. Premium
Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.
Exercici 5 - Viatjant de comerç · Juny 2026 ›