Exercici 4 · Matemática Discreta UAB 2025

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í