Examen de Matemática Discreta UAB 2026 · Juny

Exercici 1 (2 punts). Poliedre convex i cares

Considerem un poliedre convex format per 60 vèrtexs, en el qual totes les cares són triangles, quadrilàters o pentàgons. Cada vèrtex té grau 4 (és a dir, a cada vèrtex hi concorren exactament 4 cares). A més, se sap que el poliedre conté exactament 20 cares triangulars.

a.

[0,5 punts] Calculeu el nombre total d'arestes del poliedre.

b.

[0,5 punts] Determineu quantes cares té en total.

c.

[1 punt] Calculeu el nombre de quadrilàters i de pentàgons que té el poliedre.

Exercici 2 (2,5 punts). Polinomis cromàtics i propietats espectrals

a.

(1,5 punts) Sigui $G$ el graf format per la unió disjunta d'un arbre $T$ de 6 vèrtexs, el graf complet $K_5$ i dos vèrtexs aïllats, és a dir, $G = T \cup K_5 \cup \{v_1, v_2\}$.

Nota: Podeu deixar els polinomis cromàtics en forma factoritzada sense desenvolupar.

1.

(0,5 punts) Determineu el polinomi cromàtic de l'arbre $T$ i el de $K_5$.

2.

(0,25 punts) Determineu el polinomi cromàtic del graf $G$.

3.

(0,5 punts) Calculeu el nombre cromàtic de $G$, justificant el resultat a partir del nombre cromàtic de cadascuna de les seves components connexes.

4.

(0,25 punts) De quantes maneres es pot acolorir el graf $G$ utilitzant el nombre mínim de colors? Podeu expressar el resultat en forma factoritzada.

b.

(1 punt) El polinomi cromàtic d'un graf simple $D$ ve donat per:

$$f(D, t) = t^{13} - 11t^{12} + at^{11} - 131t^{10} + 205t^9 - 201t^8 + 121t^7 - 41t^6 + 6t^5$$

1.

(0,6 punts) Quants vèrtexs, quantes arestes i quantes components connexes té el graf $D$?

2.

(0,4 punts) Calculeu el valor del coeficient $a$.

Exercici 3 (2 punts). Grafs eulerians i hamiltonians

a.

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

b.

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

c.

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

d.

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

Exercici 4 (2,5 punts). Problema del carter xinès

Un servei municipal ha de recórrer tots els carrers d'un barri per fer una inspecció i tornar al punt d'inici. El barri es representa mitjançant el següent graf ponderat, on els pesos indiquen la longitud dels carrers en minuts:

$$V = \{A, B, C, D, E, P, G, H, U, J\}$$

Partint del vèrtex A, trobeu el circuit tancat de cost mínim que passa com a mínim una vegada per cada aresta del graf.

a)

[0,5 punts] Indiqueu a quin problema clàssic correspon i el nom de l'algorisme o mètode vist a classe que el resol.

b)

[2 punts] Mostreu detalladament tots els passos de l'algorisme. Indiqueu finalment:

Una empresa de repartiment ha de distribuir material a diverses poblacions d'una comarca. Cada dia, un vehicle surt del magatzem central, ha de visitar totes les poblacions exactament una vegada i tornar finalment al punt d'origen, intentant minimitzar la distància total recorreguda. Es disposa de les distàncies entre totes les poblacions i el magatzem central de l'empresa.

a.

(0,2 punts) Expliqueu com es pot modelitzar aquesta situació mitjançant un graf ponderat. Indiqueu què representen els vèrtexs, les arestes i els pesos de les arestes.

b.

(0,2 punts) Quin problema clàssic de teoria de grafs o optimització representa aquesta situació? Indiqueu les condicions que ha de satisfer una ruta vàlida en aquest problema.

Una empresa de repartiment ha de distribuir material a diverses poblacions d'una comarca. Cada dia, un vehicle surt del magatzem central, ha de visitar totes les poblacions exactament una vegada i tornar finalment al punt d'origen, intentant minimitzar la distància total recorreguda. Es disposa de les distàncies entre totes les poblacions i el magatzem central de l'empresa.

c.

(0,3 punts) Suposeu ara que l'empresa vol construir una xarxa pròpia de comunicacions entre totes les poblacions. El cost de connectar dues poblacions és proporcional a la distància entre elles i es vol que totes les poblacions quedin connectades amb el cost total mínim possible. Indiqueu quin problema de teoria de grafs modelitza aquesta situació i esmenteu un algorisme que permeti resoldre'l.

Una empresa de repartiment ha de distribuir material a diverses poblacions d'una comarca. Cada dia, un vehicle surt del magatzem central, ha de visitar totes les poblacions exactament una vegada i tornar finalment al punt d'origen, intentant minimitzar la distància total recorreguda. Es disposa de les distàncies entre totes les poblacions i el magatzem central de l'empresa.

d.

(0,3 punts) A causa d'unes obres, algunes carreteres queden tallades. Expliqueu com es podria determinar si encara és possible arribar des del magatzem a totes les poblacions de la comarca. Indiqueu quin problema de teoria de grafs modelitza aquesta situació i esmenteu un algorisme que permeti resoldre'l.