Université d’Alger 1

Benyouçef benkhedda

Theorie des graphes : P roblè me d e

l’arb re c ou vran t d e p oid s min imal

Présenté par
Dr. BOUFENAR Chaouki
Maître de Conférences, Université Alger 1
[email protected]

2022/2023
Problème de l’arbre couvrant de poids minimal (Minimum Spanning Tree)
 On dispose d’un graphe G Connexe et on associe à ses arêtes des poids (couts ou valeurs).

 Il s’agit donc de trouver un graphe partiel qui soit un arbre et pour lequel la somme des poids de ces arcs soit
minimale.
Exemple

• Conception de circuits électroniques : pour interconnecter les broches de composants électriquement équivalents

On peut modéliser ce problème de câblage à l’aide d’un graphe non orienté connexe 𝐺 = X, U tel que :

𝐗 : représente l’ensemble des broches

𝐔: l’ensemble des interconnections possibles entre paires de broches
𝐏𝐨𝐢𝐝𝐬 : longueur de fil nécessaire pour connecter les broches
On souhaite alors trouver un sous-ensemble acyclique (sans cycle) 𝐓 ⊆ 𝐔 qui connecte tous les sommets et dont le
poids total soit minimum.

𝐓 est acyclique et connecte tous les sommets, il doit former un arbre, que l’on appelle arbre couvrant car il « couvre » le
graphe 𝑮.
Problème de l’arbre de poids minimal (Minimum Spanning Tree)
Exemple
 On peut avoir plusieurs arbres de differents poids à partir d’un graphe connexe valuè.
a 𝟖 b

3
𝟑 𝑷𝒐𝒊𝒅𝒔 𝒎𝒊𝒏: 8 + 2 + 3 + 3 = 𝟏𝟔
a b c d
𝟖
𝟐
5
3
6 e
1
c 𝟑 d
𝟏𝟏
𝟐

e a b
𝟖
Graphe connexe valuè
5 6

c d 𝑷𝒐𝒊𝒅𝒔 𝒎𝒊𝒏: 5 + 8 + 11 + 6 =30

𝟏𝟏

e
 Problème de l’arbre couvrant de poids minimal
Algorithme de Kruskal
Entrée : Un graphe 𝐺 = 𝑋, 𝑈, 𝑐 tel que :
𝑿 = 𝑛 ; 𝑼 = 𝑝 ; c : function de cout (c ∶ 𝑈 → 𝑅 )
Sortie: Un ensemble 𝑨 contenant les arcs de l’arbre du poids minimal
Début
Numéroter les arcs par ordre croissant des poids
c 𝑢1 ≤ c 𝑢2 ≤ c 𝑢3 ≤ ... ≤ c 𝑢𝑝
𝐴←∅ 𝑗←0
Pour i=1 à (𝑛-1) Faire (Tant que j < 𝑛 Faire) \\ en rouge une version optimisée
Si 𝐴 ∪ 𝑢𝑖 𝑛𝑒 𝑐𝑜𝑚𝑝𝑜𝑟𝑡𝑒 𝑝𝑎𝑠 𝑑𝑒 𝑐𝑦𝑐𝑙𝑒 Alors
𝐴 ← 𝐴 ∪ 𝑢𝑖
𝑗 ←𝑗+1
Fin Si
Fin Pour (Tant que)
𝑿, 𝑨 𝑒𝑠𝑡 𝑙 ′ 𝑎𝑟𝑏𝑟𝑒 𝑑𝑢 𝑝𝑜𝑖𝑑𝑠 𝑚𝑖𝑛𝑖𝑚𝑎𝑙
Fin
 Problème de l’arbre couvrant de poids minimal
Exemple Algorithme de Kruskal
𝒖𝟕
a 𝟖
b
a b a b a b
5 𝒖𝟔
𝒖𝟓 𝒖𝟒 𝒖𝟏 6 1 1
3
1 1
c 𝟑
𝟑 d c d c d
c 𝒖𝟑 d 𝟐 𝟐
𝒖𝟐 𝟏𝟏
𝟐
𝒖𝟖 e e e
e i=1 i=2 i=3

a b a b a b a 𝟖 b a b

5 6
3 3 3 3 3
1 1 1 1 1
𝟑 𝟑 𝟑 𝟑 𝟑
c d c d c d c d c d
𝟐 𝟐 𝟐 𝟐 𝟐 𝟏𝟏

e e e e e
i=4 i=5 i=6 i=7 i=8
Arrêt Arrêt
J=4 𝑷𝒐𝒊𝒅𝒔 𝒎𝒊𝒏: 1 + 2 + 3 + 3 = 𝟗 i=n=8
 Problème de l’arbre couvrant de poids minimal
Algorithme de Prim
Entrée : Un graphe 𝐺 = 𝑋, 𝑈, 𝑐 tel que :
𝑿 = 𝑛 ; 𝑼 = 𝑝 ; c : function de cout (c ∶ 𝑈 → 𝑅 )
Sortie: Un graphe T= 𝑋′, 𝐴

Début
𝐴←∅
X′ ← 𝑥 𝜖𝑋 ; 𝑥 un sommet de G qu’on choisit
Repeter
• Trouver toutes les arêtes de G qui relient un sommet de T et un sommet exterieur à T
• Parmi celles − ci, choisir une arête de poids min 𝑠𝑜𝑖𝑡 𝒖 𝑐𝑒𝑡𝑡𝑒 arête
• Ajouter à T cette arête et le sommet correspondant 𝑠𝑜𝑖𝑡 𝒙 𝑐𝑒 𝑠𝑜𝑚𝑚𝑒𝑡

𝐴 ← 𝐴 ∪ 𝑢 , X′ ← X′ ∪ 𝑥′
Jusqu’à ce que tous les sommets de G soient dans T
𝑅𝑒𝑡𝑜𝑢𝑟𝑛𝑒𝑟 T
Fin
 Problème de l’arbre couvrant de poids minimal
Exemple Algorithme de Prim
a 𝟖
b a b a b a b
𝟖 𝟖 𝟖

5 5 5
6 5 6
3 6
1 1 1
1
𝟑 𝟑
c d c d c 𝟑
d c d
𝟏𝟏 𝟏𝟏
𝟐 𝟐 𝟐
𝟐

e e e e
a 𝟖
b
a b
6 𝑷𝒐𝒊𝒅𝒔 𝒎𝒊𝒏: 1 + 2 + 3 + 3 = 𝟗
3
1
𝟑 3
c d 1
𝟑
𝟐 c d
𝟐

e e