Pregunta 3 (apartats a, b, c) - Grafs hamiltonian… · Matemática Discreta UAB 2024
Tema: Grafs eulerians i hamiltonians · 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:
a.
És hamiltonià aquest graf? Justifiqueu la resposta.
Sí
No
b.
És eulerià? Justifiqueu la resposta.
Sí
No
c.
Conté algun camí eulerià? Justifiqueu la resposta.
Sí
No
Solución
Según los criterios oficiales de corrección
a. És hamiltonià aquest graf?
Solución: No
Justificació de l'apartat a
Solución: Els vèrtexs imparells de l'anell exterior tenen grau 2, forçant a recórrer totes les arestes de l'anell exterior i tancant el cicle abans de visitar el vèrtex central 13.
b. És eulerià? Justifiqueu la resposta.
Solución: No
Justificació de l'apartat b
Solución: Un graf connex és eulerià si i només si tots els seus vèrtexs tenen grau parell. Els vèrtexs {2, 4, 6, 8, 10, 12} tenen grau 3 (imparell).
c. Conté algun camí eulerià? Justifiqueu la resposta.
Solución: No
Justificació de l'apartat c
Solución: Per admetre un camí eulerià cal que el nombre de vèrtexs de grau imparell sigui exactament 0 o 2. Com que en té 6, no admet camí eulerià.
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 3 · Juny 2026 · Pregunta 3 · 2023 ›