Ejercicios de Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra)

5 ejercicios de Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra) que han salido en los exámenes de Matemática Discreta de la…

Exercici 5 - Arbre generador de cost mínim · Juny 2026

Exercici 5, apartat c: Indicar quin problema de teoria de grafs modelitza connectar totes les poblacions amb cost total mínim i anomenar un algorisme per resoldre'l.

Exercici 4 · 2025

Es dóna una matriu de distàncies entre 8 pobles (A a H). Es demana trobar la longitud mínima de l'arbre d'expansió mitjançant l'algorisme de Kruskal detallant la selecció d'arestes, i determinar si és possible un circuit tancat usant exclusivament aquests camins.

Exercici 5 · 2025

Exercici 5 (3 punts). Anàlisi de l'evolució de l'algorisme de Dijkstra a partir d'una taula de distàncies provisionals i vèrtexs visitats: determinar camí mínim d'A a D i el seu cost, compatibilitat de l'aresta (A, G) de pes 10, arbre de camins mínims i predecessors, recorreguts BFS i DFS ordenats alfabèticament, i…

Exercici 4 · 2023

Preguntes teòriques sobre l'algorisme de Floyd-Warshall per a camins mínims entre tots els parells de vèrtexs i detecció de cicles de cost negatiu.

Exercici 5 · 2023

En relació amb els algorismes clàssics d'optimització sobre grafs: a. Diferencieu el problema del camí mínim d'origen únic (Dijkstra) del problema de l'arbre d'extensió mínim (Kruskal o Prim). b. Expliqueu breument per què Dijkstra pot fallar si el graf conté arestes amb pesos estrictament negatius.

Otros temas de Matemática Discreta

Combinatòria i relacions

Grafs, arbres i recorreguts

Camins, circuits i rutes

Planaritat i coloració