Pregunta 3 · Matemática Discreta UAB 2023
Tema: Grafs eulerians i hamiltonians · Del examen Examen Segon Parcial 2023-2024 (2023)
Enunciado
Pregunta 3 (0,5 punts). Propietats eulerianes i hamiltonianes
a.
Sigui un graf bipartit complet que té exactament 16 arestes.
1.
És aquest graf eulerià?
2.
Si tenim la certesa que és hamiltonià, quants vèrtexs conté en total?
b.
Emprant les condicions necessàries o suficients estudiades, analitzeu i justifiqueu si pot ser hamiltonià un graf pla que conté 21 regions fitades per 5 arestes, 3 regions fitades per 8 arestes i la cara exterior envoltada per 9 arestes.
Solución
Según los criterios oficiales de corrección
a. 1. És aquest graf eulerià?
Solución: És eulerià si i només si tant com són parells (és a dir, per a i sí que ho és, però per a no ho és).
a. 2. Si tenim la certesa que és hamiltonià, quants vèrtexs conté en total?
Solución: 8
b. Emprant les condicions necessàries o suficients estudiades, analitzeu i justifiqueu si pot ser hamiltonià un graf pla que conté 21 regions fitades per 5 arestes, 3 regions fitades per 8 arestes i la cara exterior envoltada per 9 arestes.
Solución: No pot ser hamiltonià perquè no compleix la condició necessària del teorema de Grinberg.
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.
‹ Pregunta 3 (apartats a, b, c) - Grafs hamiltonian… · 2024 · Ejercicio 3 · Juny 2022 ›