Chapitre2 : Arbre couvrant de poids minimum
I. Arbres
On suppose que le graphe est non orienté sauf contre-indication.
1. Préliminaires
Théorème
Soit G(X,E) un graphe d’ordre n
1. Si G est connexe alors |E|≥n-1
2. Si G est sans cycle alors |E|≤n-1
Définition
Un arbre est un graphe connexe et sans cycle, donc il admet (n-1) arêtes.
Corollaire
Un graphe connexe possède un graphe partiel qui est un arbre.
Définition
Un sommet pendant est un sommet de degré 1.
Théorème
Un arbre contient au moins 2 sommets pendants.
II. Problème de l’arbre couvrant de poids minimum
Définition
Soit G=(X,E) un graphe connexe et simple et p l’application :
P:Eℝ
ep(e)
P(e) s’appelle poids de l’arête e.
Si G’=(X,E’) est un graphe partiel de G alors p(G’)= ∑
Par convention : Si E’= alors p(G’)=0
Exemple :
Soit le graphe G(X,E) suivant : n=4 ; m=5
P(G)=0
E’={(ac),(bc),(bd)}
G’=(X,E’) p(G’) = p(ac)+p(bc)+p(bd)=1+0+(-1)=0 (G’ : graphe partiel de G qui est un
arbre de poids minimum)
Problématique :
Trouver un graphe partiel de G qui est un arbre de poids minimum
Solutions :
- Algorithme de Kruskal
- Algorithme de Prim
A. Algorithme de Kruskal
Les arêtes du graphe G(X, E) sont supposées numérotées suivant l’ordre croissant de
leurs poids : p(e1)≤p(e2) ≤p(e3) ≤… ≤p(em)
Pseudo-code :
Poser E’= et i=1
1.a. Si(X,E’ {ei}) contient un cycle aller en 3.
b. Sinon, aller en 2.
2. Poser E’← E’ {ei} et aller en 3.
3. a. Si (|E’|=n-1) alors terminer
b. Sinon, i←i+1 et aller en 1.
Le graphe G’(X,E’) est un arbre de poids minimum
Exemple :
Soit le graphe G(X,E) suivant : n=5 ; m=7
p(e1)≤p(e2) ≤p(e3) ≤… ≤p(em)
Trouver un graphe partiel de G qui est un arbre de poids minimum en utilisant
l’algorithme de Kruskal
Exécution :
E’= ; i=1
(X,{e1}) ne contient pas un cycle E’={e1} ; i=2
E’={e1}; i=2
(X,{e1, e2}) ne contient pas un cycle E’={e1, e2}; i=3
E’={e1, e2}; i=3
(X,{e1, e2, e3}) ne contient pas un cycle E’={e1, e2, e3}; i=4
E’={e1, e2, e3}; i=4
(X,{e1, e2, e3, e4}) contient un cycle E’={e1, e2, e3}(pas de m-à-j); i=5
E’={e1, e2, e3}; i=5
(X,{e1, e2, e3, e5}) ne contient pas un cycle E’={e1, e2, e3,e5}; |E’|=4=n-1
arrêt de l’algorithme
Le graphe G’(X,E’) suivant est un arbre de poids minimum, p(G’)=-2-
1+1+4=2
Algorithme de Prim
Pseudo-code :
X={x1,x2,…,xn}
Sv←{x1}// Sv : Ensemble de sommet traités
Ea← // Ensemble d’arètes de l’arbre de poids minimum
Pour i de 1 à |X|-1 faire
Choisir une arête e entre les sommets u et v tel que uSv et vX-Sv avec e de
poids minimum
Ea←Ea {e}
Sv←Sv {v}
Fin Pour
Exemple :
Soit le graphe G(X, E) suivant ; |X|=n=6 ; |E|=m=10
Trouver un graphe partiel de G qui est un arbre donc admettant 5 arêtes en
utilisant l’algorithme de Prim
Méthode simple :
a b c d e f
a 0 3 ∞ ∞ 6 5
b 3 0 1 ∞ ∞ 4
c ∞ 1 0 6 ∞ 4
d ∞ ∞ 6 0 8 5
e 6 ∞ ∞ 8 0 2
f 5 4 4 5 2 0
G’ (X,E’) avec E’={(ab),(bc),(bf),(fe),(fd)} est un arbre de poids minimum.
