Exercici 5 - Recorreguts BFS i DFS · Matemática Discreta UAB Juny 2026
Tema: Recorreguts BFS i DFS · Del examen Juny (2026)
Enunciado
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.
Solución
Según los criterios oficiales de corrección
Indiqueu quin problema de teoria de grafs modelitza aquesta situació
Solución: Problema de connexió / d'accessibilitat / connexitat en grafs
esmenteu un algorisme que permeti resoldre'l.
Solución: Cerca en amplada (BFS) / Cerca en profunditat (DFS)
Expliqueu com es podria determinar si encara és possible arribar des del magatzem a totes les poblacions de la comarca.
Solución: Es pot resoldre executant un algorisme d'exploració de grafs, com ara una cerca en amplada (BFS) o una cerca en profunditat (DFS), prenent com a vèrtex inicial el magatzem. Si el nombre de vèrtexs visitats durant el recorregut coincideix amb el total de vèrtexs del graf, serà possible arribar a totes les poblacions; en cas contrari, algunes poblacions hauran quedat aïllades o inaccessibles.
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.