Arbre couvrant minimal — algorithme de Kruskal

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

Énoncé et solution adaptés au programme français. Voir crédits.

Énoncé

Graphe pondéré à 5 sommets : ${1, 3} (1)$ , ${3, 5} (2)$ , ${2, 4} (3)$ , ${3, 4} (4)$ , ${2, 3} (5)$ , ${1, 2} (6)$ , ${4, 5} (7)$ .

Appliquer Kruskal et donner le poids total de l'arbre couvrant minimal.

— clique pour révéler

1 Indice 1

L'algorithme de Kruskal consiste a trier toutes les aretes par poids croissant, puis a les ajouter une a une a l'arbre en cours de construction.

2 Indice 2

N'ajoute une arete que si elle ne cree pas de cycle avec les aretes deja selectionnees, sinon passe a l'arete suivante.

3 Indice 3

Continue jusqu'a avoir selectionne exactement $n-1$ aretes pour un graphe a $n$ sommets, puis additionne les poids des aretes retenues.

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Validez votre réponse pour enregistrer votre progression et gagner des points