CHAPITRE 2
PROBLÈME DE L’ARBRE COUVRANT DE COÛT MINIMUM
Théorie des Graphes et Optimisation 1
Problème de l’arbre couvrant de coût minimum I. Introduction
Problème de l’Arbre Couvrant de Coût minimum
Réalisation d’un réseau électrique
Modélisation par un graphe non orienté valué
Poids d'une arête : le coût (ex. longueur de câble) de construction de la portion du réseau reliant deux
points
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
Quelles sont les liaisons à réaliser pour connecter toutes les villes au moindre coût ?
Théorie des Graphes et Optimisation 2
Problème de l’arbre couvrant de coût minimum I. Introduction
Problème de l’Arbre Couvrant de Coût minimum
Contraintes d'optimisation de réalisation d’un réseau électrique
Deux villes quelconques doivent être reliées entre elles (connexité)
Graphe partiel connexe
5
A B
4 6 2
C 2 D 3
3 1 2
E F
Il doit y avoir une seule chaine qui relie deux villes quelconques 4
graphe partiel connexe sans cycle
Théorie des Graphes et Optimisation 3
Problème de l’arbre couvrant de coût minimum I. Introduction
Problème de l’Arbre Couvrant de Coût minimum
Contraintes d'optimisation de réalisation d’un réseau électrique
Minimiser le coût du réseau représenté par un graphe partiel connexe sans cycles
(arbre) couvrant
coût =10 coût =18
5 5
A B A B
4 6 2 4 6 2
C 2 D 3 C 2 D 3
3 1 2 3 1 2
E F E F
4 4
Déterminer l’Arbre Couvrant de Coût Minimum (ACCM)
Théorie des Graphes et Optimisation 4
Problème de l’arbre couvrant de coût minimum II. Définitions
Arbre
Un arbre est un graphe non orienté, connexe, sans cycles
A B
C D
E F
Théorie des Graphes et Optimisation 5
Problème de l’arbre couvrant de coût minimum II. Définitions
Arbre
Caractérisations d'un Arbre : Pour un arbre T d'ordre n, il y a équivalence entre les
propriétés :
1. T est un arbre
2. T est un graphe connexe à n-1 arêtes
3. T est connexe, et la suppression de toute arête le déconnecte
4. T est acyclique à n-1 arêtes
5. T est acyclique et l'ajout de toute arête le rend cyclique.
Théorie des Graphes et Optimisation 6
Problème de l’arbre couvrant de coût minimum II. Définitions
Arbre couvrant
Soit G un graphe valué non orienté connexe. Un arbre couvrant est un graphe partiel
de G couvrant (i.e. contenant tous les sommets), connexe et sans cycles. Son coût est
la somme des valuations de ses arêtes.
Arbre couvrant T1: Coût(T1) =18 Arbre non couvrant T2: Coût(T2) =13
5
A B 5
4 A B
6 2 4 6 2
C 2 D 3
C 2 D 3
3 1 2
E F 3 1 2
4 E F
4
Théorie des Graphes et Optimisation 7
Problème de l’arbre couvrant de coût minimum II. Définitions
Arbre couvrant de coût minimum
Un Arbre Couvrant de Coût Minimum (ACCM) est un arbre couvrant dont le coût est le
plus petit possible parmi les arbres couvrants de G.
Arbre couvrant de coût minimum T*: Coût(T*) =10
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
Théorie des Graphes et Optimisation 8
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Kruskal
Principe:
1. Trier toutes les arêtes et les placer en ordre croissant de coût (arbre de valeurs
minimales).
2. Choisir l’arête ayant le plus petit coût .
3. Répéter l’étape 2 jusqu’à ce que tous les sommets soient reliés (m = n-1) en évitant
celles qui formeraient un cycle
Théorie des Graphes et Optimisation 9
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Kruskal
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
❑ Trier les arêtes par ordre croissant de coût
(D,E) - (B,D) - (A,E) - (D,F) - (B,F) - (C,E) - (A,C) - (E,F) - (A,B) - (A,D)
1 - 2 - 2 - 2 - 3 - 3 - 4 - 4 - 5 - 6
Théorie des Graphes et Optimisation 10
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Kruskal
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
❑ Itération 1 : choisir l’arête (E,D)
(D,E) - (B,D) - (A,E) - (D,F) - (B,F) - (C,E) - (A,C) - (E,F) - (A,B) - (A,D)
1 - 2 - 2 - 2 - 3 - 3 - 4 - 4 - 5 - 6
Théorie des Graphes et Optimisation 11
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Kruskal
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
❑ Itération 3 : Choisir l’arête (D,B)
(D,E) - (B,D) - (A,E) - (D,F) - (B,F) - (C,E) - (A,C) - (E,F) - (A,B) - (A,D)
1 - 2 - 2 - 2 - 3 - 3 - 4 - 4 - 5 - 6
Théorie des Graphes et Optimisation 12
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Kruskal
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
❑ Itération 4 : Choisir l’arête (E,A)
(D,E) - (B,D) - (A,E) - (D,F) - (B,F) - (C,E) - (A,C) - (E,F) - (A,B) - (A,D)
1 - 2 - 2 - 2 - 3 - 3 - 4 - 4 - 5 - 6
Théorie des Graphes et Optimisation 13
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Kruskal
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
❑ Itération 5 : Choisir l’arête (D,F)
(D,E) - (B,D) - (A,E) - (D,F) - (B,F) - (C,E) - (A,C) - (E,F) - (A,B) - (A,D)
1 - 2 - 2 - 2 - 3 - 3 - 4 - 4 - 5 - 6
Théorie des Graphes et Optimisation
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Kruskal
Exemple
5
A B
4 6 2
2 D 3 cycle!!
C
3 1 2
E F
4
❑ Itération 6 : Éliminer l’arête (B,F)
(D,E) - (B,D) - (A,E) - (D,F) - (B,F) - (C,E) - (A,C) - (E,F) - (A,B) - (A,D)
1 - 2 - 2 - 2 - 3 - 3 - 4 - 4 - 5 - 6
Théorie des Graphes et Optimisation 15
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Kruskal
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
❑ Itération 7 : Choisir l’arête (C,E)
(D,E) - (B,D) - (A,E) - (D,F) - (B,F) - (C,E) - (A,C) - (E,F) - (A,B) - (A,D)
1 - 2 - 2 - 2 - 3 - 3 - 4 - 4 - 5 - 6
Théorie des Graphes et Optimisation 16
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Kruskal
Exemple
A B
2
C 2 D
3 1 2
E F
❑ Algorithme est fini : nombre d’arêtes =nombre de sommets -1
(D,E) - (B,D) - (A,E) - (D,F) - (B,F) - (C,E) - (A,C) - (E,F) - (A,B) - (A,D)
1 - 2 - 2 - 2 - 3 - 3 - 4 - 4 - 5 - 6
Non utilisées
Théorie des Graphes et Optimisation 17
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Kruskal
Algorithme
Théorie des Graphes et Optimisation 18
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Prim
Principe:
1. Initialiser les sommets d’un sous arbre T à un sommet quelconque
2. Ajouter au sous-arbre T l’arête de coût minimal connectant un sommet de T à un
sommet qui n’est pas dans T.
3. Répéter l’étape 2 jusqu’à ce que tous les sommets soient dans T
Théorie des Graphes et Optimisation 19
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Prim
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
❑ Initialiser un sous arbre T au sommet A
Théorie des Graphes et Optimisation 20
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Prim
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
❑ Itération 1 : choisir l’arête du coût minimal (A,E)
Théorie des Graphes et Optimisation 21
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Prim
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
❑ Itération 2 : choisir l’arête (E,D)
Théorie des Graphes et Optimisation 22
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Prim
Exemple Arête connectant deux sommets
de l’arbre est élimée
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
❑ Itération 3 : choisir l’arête (D,F)
Théorie des Graphes et Optimisation 23
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Prim
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
❑ Itération 4 : choisir l’arête (D,B)
Théorie des Graphes et Optimisation 24
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Prim
Exemple
5
A B
4 6 2
C 2 D 3
3 1 2
E F
4
❑ Itération 5 : choisir l’arête (E,C)
Théorie des Graphes et Optimisation 25
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Prim
Exemple
A B
2
C 2 D
3 1 2
E F
❑ Algorithme est fini : nombre d’arêtes =nombre de sommets -1
Théorie des Graphes et Optimisation 26
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Algorithme de Prim
Algorithme
Théorie des Graphes et Optimisation 27
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Application
Déterminer l’arbre de coût minimum
4
A B C
2 6 3 3 8
D 1 E 6 F 4
5 5 4 5 2
G 10
H I
MÉTHODE : Algorithme de Kruskal
1 – 2 – 2 – 3 – 3 – 4 – 4 – 4 – 5 – 5 – 5 – 6 – 6 – 8 – 10
inutiles
Poids de l’arbre : 1 + 2 + 2 + 3 + 3 + 4 + 5 + 5 = 25
Théorie des Graphes et Optimisation 28
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Application
Déterminer l’arbre de coût maximum
4
A
A B C
2 6 3 3 8
D 1 E
E 6 F 4
5 5 4 5 2
G
G H
H I
10
MÉTHODE : Algorithme de Kruskal
10 – 8 – 6 – 6 – 5 – 5 – 5 – 4 – 4 – 4 – 3 – 3 – 2 – 2 – 1
inutiles
Coût de l’arbre : 10 + 8 + 6 + 6 + 5 + 5 + 4 + 4 = 48
29
Théorie des Graphes et Optimisation
Problème de l’arbre couvrant de coût minimum III. Recherche de l’arbre couvrant de coût minimum
Application
Déterminer l’arbre de coût minimum
4
A B C
2 6 3 3 8
D 1 E 6 F 4
5 5 4 5 2
G 10
H I
MÉTHODE : Algorithme de Prim
Coût de l’arbre : 2 + 4 + 1 + 3 + 3 + 5 + 2 + 5 = 25
Théorie des Graphes et Optimisation 30
