Arbres couvrants

Un arbre couvrant (ou arbre maximal) est un graphe partiel qui est aussi un arbre. Ci-contre, un des arbres couvrants (en bleu) d'un graphe donné.

Arbre maximal de poids minimum

On considérera le problème suivant :
Soit le graphe G = (V, E) avec un poids associé à chacune de ses arêtes. Trouver, dans G, un arbre maximal A = (V, F) de poids total minimum.

L'algorithme de Kruskal

Données : Graphe G = (V, E) (|V| = n, |E| = m) et pour chaque arête e de E, son poids c(e).
Résultat : Arbre ou forêt maximale A = (V, F) de poids minimum.

Trier et renuméroter les arêtes de G dans l'ordre croissant de leur poids : c(e1) c(e2) ... c(em).
Poser F := Ø, k := 0
Tant que k < m et |F| < n-1 faire
   Début
      si ek+1 ne forme pas de cycle avec F alors F := F U {ek+1}
      k := k+1
   Fin

Ce problème se pose, par exemple, lorsqu'on désire relier n villes par un réseau routier de coût minimum. Les sommets du graphe représentent les villes, les arêtes, les tronçons qu'il est possible de construire et les poids des arêtes correspondent aux coûts de construction du tronçon correspondant. L'algorithme de Kruskal décrit ci-dessus permet de résoudre ce problème.

Exercices

Exercice 1
Combien d'arbres couvrants différents les graphes suivants possèdent-ils ?

a. b. c.
Exercice 2
Trouvez tous les arbres maximaux de poids minimum du graphe ci-dessous (les chiffres en bleu représentent le poids des arêtes):

Les corrigés sont disponibles, mais seulement pour les visiteurs autorisés!
Mot de passe :

Références

Didier Müller, 9.2.03