Ejercicios de Grafs eulerians i hamiltonians

4 ejercicios de Grafs eulerians i hamiltonians que han salido en los exámenes de Matemática Discreta de la UAB (Grado en Ingeniería Informática) 2022-2026.

Exercici 3 · Juny 2026

Exercici 3 (2 punts). Grafs eulerians i hamiltonians: a) Determinar si G1 és eulerià i si té camí eulerià. b) Demostrar que el complementari d'un graf d-regular d'ordre n >= 2d + 2 és hamiltonià. c) Determinar si G2 és eulerià en funció de d. d) Determinar si el graf G8 és hamiltonià utilitzant criteris de classe.

Pregunta 3 (apartats a, b, c) - Grafs hamiltonian… · 2024

Determinar i justificar si el graf de 13 vèrtexs és hamiltonià (a), eulerià (b) o si conté algun camí eulerià (c).

Pregunta 3 · 2023

Pregunta 3: Propietats eulerianes i hamiltonianes en grafs bipartits complets i aplicació del teorema de Grinberg en un graf pla.

Ejercicio 3 · Juny 2022

a. Justifica que si K_{m,n} es euleriano, su número de aristas es múltiplo de 4. b. Usando el teorema de Grinberg, justifica si puede ser hamiltoniano un grafo plano con 7 caras interiores de 3 aristas, 4 de 4 aristas y una cara exterior de 8 aristas.

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
• Optimització de rutes: carter xinès, viatjant de comerç i complexitat · 8 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