Exercici 3 · Matemática Discreta UAB Juny 2026

Tema: Grafs eulerians i hamiltonians · Del examen Juny (2026)

Enunciado

Exercici 3 (2 punts). Grafs eulerians i hamiltonians

a.

(0,5 punts) Sigui G1G_1 un graf simple connex amb seqüència de graus (6,5,4,4,4,3,2,2,2)(6, 5, 4, 4, 4, 3, 2, 2, 2). Determineu si G1G_1 és eulerià i si conté algun camí eulerià.

b.

(0,5 punts) Sigui G2G_2 un graf dd-regular d'ordre n≥2d+2n \ge 2d + 2, amb d≥1d \ge 1. Demostreu que el graf complementari G2‾\overline{G_2} és hamiltonià utilitzant algun dels criteris vistos a classe.

c.

(0,5 punts) Determineu si el graf G2G_2 de l'apartat anterior és eulerià en funció de dd.

d.

(0,5 punts) Utilitzant algun dels criteris vistos a classe, determineu si el graf G8G_8 representat a continuació és hamiltonià:

Enunciado: Exercici 3 · Matemática Discreta UAB Juny 2026

Solución

Según los criterios oficiales de corrección

a. Determineu si G_1 és eulerià i si conté algun camí eulerià.

Solución: G1G_1 no és eulerià, però sí que conté un camí eulerià.

b. Demostreu que el graf complementari \overline{G_2} és hamiltonià utilitzant algun dels criteris vistos a classe.

Solución: Pel teorema de Dirac, com que per a tot vèrtex grau⁡G2‾(v)=n−1−d≥n2\operatorname{grau}_{\overline{G_2}}(v) = n - 1 - d \ge \frac{n}{2}, el graf complementari G2‾\overline{G_2} és hamiltonià.

c. Determineu si el graf G_2 de l'apartat anterior és eulerià en funció de d.

Solución: G2G_2 és eulerià si dd és parell, i no és eulerià si dd és senar.

d. Utilitzant algun dels criteris vistos a classe, determineu si el graf G_8 representat a continuació és hamiltonià:

Solución: El graf G8G_8 no és hamiltonià.

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 ›

Más ejercicios de Grafs eulerians i hamiltonians