Examen de Matemática Discreta UAB 2025 · Parcial 1 – Matemàtica Discreta (Curs 2025-2026)

Exercici 1 (2 punts). Mosaics RGB i combinatòria

Una família de l'època clàssica es dedica a la venda de mosaics RGB d'alta definició (formats per tessel·les Vermelles, Verdes i Blaves). Flavio Mínimo s'encarrega de carregar al magatzem lloses quadrades fins a l'obra; aquestes rajoles són de tres colors possibles i les del mateix color són absolutament idèntiques entre si. A peu d'obra, Flavia Máxima munta una quadrícula o matriu de $10 \times 10$ lloses, de manera que en cada mosaic empra sempre com a mínim 10 lloses de cadascun dels tres colors.

a.

A Flavio Mínimo únicament li interessa saber la quantitat de lloses de cada color presents al mosaic, sense importar-li gens la seva posició. Quants mosaics diferents existeixen des del seu punt de vista?

b.

Per a Flavia Máxima, en canvi, la col·locació precisa de cada llosa en la quadrícula és clau (el color a cada coordenada). Quants mosaics diferents pot elaborar si disposa exactament d'un lliurament format per 40 lloses vermelles, 35 de verdes i 25 de blaves? Podeu expressar el resultat sense fer el càlcul numèric final.

Considerem la seqüència de nombres enters $x, x, x, y, y, y, y$ amb la restricció $0 < y < x \le 5$.

a.

Determineu per a quins valors de $x$ i $y$ aquesta seqüència és gràfica.

Considerem la seqüència de nombres enters $x, x, x, y, y, y, y$ amb la restricció $0 < y < x \le 5$.

b.

Identifiqueu per a quins valors de $x, y$ la seqüència correspon als graus dels vèrtexs d'un arbre.

Existeix algun graf que no sigui un arbre i que tingui exactament aquesta mateixa seqüència de graus? Justifiqueu la resposta.

Sí

No

Exercici 3 [1,25 punts]. Relació binària d'ordre i graf complementari

Sigui el conjunt $A = \{a \in \mathbb{N} \mid 1 \le a \le 5\}$. Establim sobre $A$ la relació binària $R = \{(a, b) \in A \times A \mid a < b\}$.

a)

Representeu mitjançant un dibuix el graf dirigit $G(A, R)$ que sorgeix d'aquesta relació.

b)

Dibuixeu el graf complementari $\bar{G}$.

c)

Justifiqueu de manera raonada quina relació binària genera el graf complementari $\bar{G}$.

Exercici 4 [2 punts]. Arbre d'expansió mínima mitjançant Kruskal

A l'any 2075, a causa d'intenses pedregades amb pedres de la mida de patates, una xarxa de vuit pobles (identificats de la A a la H) decideix protegir part dels seus camins amb malles protectores per permetre el trànsit en bicicleta. Com que els recursos són limitats, es vol cobrir el mínim nombre de quilòmetres possible de manera que qualsevol poble estigui comunicat amb qualsevol altre. La següent matriu d'adjacència indica les distàncies en quilòmetres entre pobles (el guió «-» indica absència de camí directe):

A

B

C

D

E

F

G

H

A

0

8

7

8

-

-

-

-

B

8

0

-

-

2

-

6

-

C

7

-

0

5

2

4

8

5

D

8

-

5

0

4

3

-

8

E

-

2

2

4

0

3

6

1

F

-

-

4

3

3

0

-

8

G

-

6

8

-

6

-

0

5

H

-

-

5

8

1

8

5

0

a)

Trobeu la longitud total mínima de malles requerida per garantir la connexió entre tots els pobles. Especifiqueu l'algorisme utilitzat i detalleu la seqüència d'arestes escollides i rebutjades durant la seva execució.

b)

Un club de ciclisme proposa dissenyar un circuit tancat que surti i acabi al mateix poble passant només per camins protegits i sense repetir cap poble pel camí. És possible organitzar aquesta ruta utilitzant exclusivament els camins mallats de l'apartat anterior? Justifiqueu la resposta.

No

Sí

Exercici 5 (3 punts). Algorisme de Dijkstra i recorreguts

La taula següent reflecteix l'evolució de l'algorisme de Dijkstra per calcular les distàncies mínimes des del vèrtex origen $A$:

Pas

$d(A)$

$d(B)$

$d(C)$

$d(D)$

$d(E)$

$d(F)$

$d(G)$

Pivot/Visitat

0 · 0 · $\infty$ · $\infty$ · $\infty$ · $\infty$ · $\infty$ · $\infty$ · $A$

1 · 0 · 18 · $\infty$ · $\infty$ · 2 · 1 · 27 · $F$

2 · 0 · 18 · $\infty$ · $\infty$ · 2 · 1 · 27 · $E$

3 · 0 · 18 · $\infty$ · $\infty$ · 2 · 1 · 16 · $G$

4 · 0 · 18 · $\infty$ · $\infty$ · 2 · 1 · 16 · $B$

5 · 0 · 18 · 19 · $\infty$ · 2 · 1 · 16 · $C$

6 · 0 · 18 · 19 · 48 · 2 · 1 · 16 · $D$

a.

Recupereu el camí de cost mínim des d'$A$ fins a $D$ i indiqueu el seu cost total.

b.

Un estudiant sosté que al graf original hi ha una aresta directa $(A, G)$ de cost 10. És compatible aquesta afirmació amb la taula? Raoneu la resposta.

Sí

No

c.

Construïu l'arbre de camins mínims amb origen a $A$ i especifiqueu el predecessor de cada vèrtex.

Predecessor de $B$:

Predecessor de $C$:

Predecessor de $D$:

Predecessor de $E$:

Predecessor de $F$:

Predecessor de $G$:

d.

Prenent com a base l'arbre de camins mínims de l'apartat anterior, escriviu un recorregut en amplada (BFS) i un recorregut en profunditat (DFS) començant des d'$A$. En cas d'haver d'escollir entre diversos veïns, processeu-los en ordre alfabètic.

e.

Suposeu que el cost de l'aresta $(B, C)$ s'incrementa d'1 a 10. Sense necessitat d'executar novament tot l'algorisme de Dijkstra, indiqueu quins vèrtexs poden veure incrementada la seva distància mínima respecte a $A$.