Pregunta 3 (apartat d) - Problema del carter xinès · Matemática Discreta UAB 2024
Tema: Optimització de rutes: carter xinès, viatjant de comerç i complexitat · Del examen Examen Segon Parcial de Matemàtica Discreta (Curs 2024-2025) (2024)
Enunciado
Considereu el graf no dirigit de 13 vèrtexs que es mostra a la figura següent, on el vèrtex central 13 està connectat als vèrtexs parells de la circumferència:
d.
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.
Solución
Según los criterios oficiales de corrección
Cost mínim del recorregut tancat:
Solución: 24
Arestes a duplicar i justificació / circuit resultant:
Solución: Arestes a duplicar: (2,3), (3,4), (6,7), (7,8), (10,11), (11,12) / Circuit: 1-2-3-4-13-6-7-8-9-10-11-12-11-10-13-8-7-6-5-4-3-2-13-12-1
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 · Pregunta 4 · 2024 ›