Exercici 5 - Arbre generador de cost mínim · Matemática Discreta UAB Juny 2026

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.