Leçon 3 : Arbres couvrants et
flots dans les graphes
Table des matières
Objectifs 3
I - Activité d’enseignement et d’apprentissage 1 : Algorithme de Prim 4
1. Définition ...................................................................................................................4
2. Algorithme de Prim pour trouver des arbres couvrant de poids minimal..................4
2.1. Principe..............................................................................................................................................5
2.2. Formalisation de l'algorithme............................................................................................................5
2.3. Exemple de Prim ...............................................................................................................................5
2
Objectifs
A la fin de cette leçon, vous serez capable :
Appliquer l'algorithme de Prim pour trouver des arbres couvrants de poids minimum
Appliquer l'algorithme de Kruskal pour trouver des arbres couvrants de poids minimum
Comprendre les concepts de flots et de coupes minimales dans les graphes
Utiliser l'algorithme de Ford-Fulkerson pour résoudre des problèmes de flots maximaux
3
Activité d’enseignement et
d’apprentissage 1 : Algorithme de Prim I
Objectifs
A la fin de cette activité, vous serez capable :
Appliquer l'algorithme de Prim pour trouver des arbres couvrants de poids minimum
1. Définition
Un arbre est une famille particulière de graphe.
Pour un arbre T à n sommets il y a équivalence entre les définitions suivantes :.
T est un arbre
T est un graphe connexe à n-1 arêtes
T est un graphe acyclique à n-1 arêtes
T est un graphe connexe et la suppression de toute arête la déconnecte
T est un graphe acyclique et l'ajout de toute arête le rend cyclique
Un graphe partiel G'(V, E') d'un graphe G(V, E) est
un graphe qui a les mêmes sommets que G
un graphe dont l'ensemble des arêtes E' est inclus dans E
Un arbre couvrant T d'un graphe G(V, E) est un graphe partiel, sans cycle
Un graphe pondéré est un graphe où un entier positif est affecté à chaque arête.
On appelle cet entier poids de l'arête
Le poids (où cout) d'un graphe est la somme des poids des arêtes du graphes.
Le poids du graphe de l'exemple ci-dessus est de 103
2. Algorithme de Prim pour trouver des arbres couvrant de poids
minimal
Algorithme de Prim
Principe
Formalisation de l'algorithme
Exemple
4
Activité d’enseignement et d’apprentissage 1 : Algorithme de Prim
2.1. Principe
L'idée principale :
Maintenir un sous graphe partiel connexe
A chaque étape connecter un nouveau sommet au sous graphe partiel existant par l'arête de poids
minimum sortante du graphes partiel Dans un arbre couvrant, il existe nécessairement une arête qui relie
l'un des sommets de S avec un sommet en dehors de S
l'algorithme de Prim va ainsi faire grossir un arbre jusqu'à ce qu'il couvre tous les sommets du graphe.
2.2. Formalisation de l'algorithme
2.3. Exemple de Prim
L'algorithme de Prim construit un arbre couvrant de poids minimum sur tout graphe connexe
