Arbres couvrants#
Sous graphes et graphes partiels#
Définition On dit qu’un graphe \(G'\) est un graphe partiel d’un graphe \(G=(V;E)\) s’il est formé par les même sommets mais un sous ensemble des arêtes de \(G\). Formellement, \(G'\) est de la forme \((V; F)\) avec \(F\subset E\).
Note : On parle parfois aussi de graphe couvrant.
Note : Ne pas confondre avec la notion de sous-graphe où l’on a aussi un sous ensemble des sommets.
Définition Étant donné un graphe \(G=(V;E)\), on appelle arbre couvrant de \(G\) un graphe \(T=(V;F)\) tel que
\(T\) est un arbre;
\(T\) est un graphe partiel de \(G\).
Intuitivement : \(T\) est construit avec les arêtes \(U\) de \(G\) en connectant (« couvre ») tous les sommets de \(V\).
Proposition 5. : Un graphe \(G=(V;E)\) admet un arbre couvrant si et seulement si il est connexe.
Preuve : Le sens direct est évident, si \(G\) admet un graphe partiel connexe alors \(G\) est connexe.
On prouve la réciproque avec l’algorithme suivant:
on pose T := G
tant que que T admet un cycle C
// Invariant : T est un graphe partiel connexe de G
supprimer dans T une arête du cycle C
renvoyer T
En effet, supprimer une arête d’un cycle d’un graphe, ne change pas sa connexité (pourquoi ?). En conséquence quand ou sort de la boucle, T contient un graphe partiel connexe et sans cycle de G.
Note : L’algorithme ci dessus n’est pas efficace. On verra ci-dessous deux algorithmes plus efficaces, dû à Kruskal et Prim.
Implanter l’algorithme ci-dessus.
Vérifier sur tous les graphes connexe que le résultat est bien un arbre.
Exercice 1. : Combien d’arbres couvrants différents les graphes ci-contre possèdent-ils ?
# VOTRE CODE ICI
raise NotImplementedError()
Arbre couvrant de poids minimum#
Soit un graphe où l’on a mis un poids sur les arêtes.
Le problème de l”arbre couvrant de poids minimum consiste à trouver un arbre couvrant dont la somme des poids \(c(e)\) des arêtes est minimum.
Ne pas confondre:
arbre couvrant de poids minimum (MST, Minimum Spanning Tree) : minimise la somme des poids des arêtes
arbre des plus courts chemins (SPT, Shortest Paths Tree) construit par exemple par BFS (Breadth First Search) ou Dijsktra : minimise la distance de la racine à chaque sommet
Voici deux arbres convrants (en rouge). Le premier est de poids \(14\), le deuxieme de poids \(10\).
Il y a deux algorithmes classiques pour calculer un arbre couvrant de poids minimum:
l’algorithme de Kruskal
l’algorithme de Prim
Algorithme de Kruskal#
Idée : On part du graphe \(T=(V, \emptyset)\) et on ajoute tour à tour la nouvelle arête de plus petit poids qui ne crée pas de cycles (i.e. qui connecte deux composantes connexes différentes).
Invariant : À l’étape \(i\), le graphe \(T\) est acyclique avec \(i\) arêtes de poids minimal
Algorithme de Prim#
Idée : On choisi un noeuds \(n\) part du graphe \(T=(\{n\}, \emptyset)\) et on ajoute tour à tour un nouveau noeud en le connectant autre en choisissant l’arête de poids minimum parmis.
Invariant : Le graphe \(T=(U,F)\) est toujours l’arbre convrant de poids minimal sur \(U\subset V\).