Arbre couvrant minimal

Propriétés d’un arbre couvrant minimal

Un arbre couvrant minimal respecte toujours certaines propriétés. Ces propriétés sont toujours vraies pour tous les MST. Connaître ces propriétés est très important, car de nombreux algorithmes y font référence pour expliquer la logique derrière leur fonctionnement.

Propriété des multiples possibles: Si certaines arêtes ont le même poids, il est alors possible qu’il y ait plusieurs MST équivalents en poids pour un graphe G.

Propriété de l’unicité: Si toutes les arêtes ont des poids distincts, alors il n’y a qu’un seul MST.

Propriété du cycle: S’il y a un cycle dans le graphe, alors l’arête la plus lourde de ce cycle ne fait pas partie du MST.

Propriété de la coupure: La coupure d’un graphe connecté est un ensemble d’arêtes qui, une fois enlevées, séparent le graphe en deux composantes disjointes. La propriété de la coupure stipule que la plus petite arête de la coupure fait partie du MST.

Propriété de l’arête de poids minimum: Si un sommet u possède une arête de poids minimum et unique, cette arête fait toujours partie du MST.

Algorithmes d’UNION-FIND

Les algorithmes d’UNION-FIND sont utilisés par les algorithmes classiques de MST (Kruskal, Borûvka). Ces algorithmes construisent le MST en ajoutant une arête et en détectant si cette arête crée un cycle ou non. Les cycles peuvent être détectés à l’aide des algorithmes d’UNION-FIND car ces derniers manipulent des structures appelées ensembles disjoints. Les ensembles disjoints permettent dans le cadre du problème du MST de gérer des groupes de sommets et ensuite savoir si une arête crée un cycle en vérifiant si cette dernière lie un groupe avec lui-même ou alors lie un groupe avec un autre groupe. Les algorithmes de UNION-FIND reposent sur deux opérations essentielles: RECHERCHE(x) et FUSION(x,y). L’opération recherche permet d’obtenir le groupe d’un élément x. L’opération Fusion permet de fusionner deux groupes. Lors de la fusion de deux ensembles disjoints, plusieurs stratégies peuvent être utilisées. L’algorithme le plus performant d’UNION-FIND utilise une compression par chemin, ce qui donne une complexité amortie de O(o(m)), la fonction Ackermann inverse. La fonction Ackermann inverse est une fonction qui croit beaucoup plus lentement qu’un logarithme.

Algorithme de Kruskal

L’algorithme de Kruskal est considéré comme l’algorithme le plus simple à comprendre et à implémenter. Kruskal conçu cet algorithme suite à la lecture du papier de Borûvka en 1956. Contrairement à l’algorithme de Borûvka et celui de Prim, l’algorithme de Kruskal nécessite auparavant le tri des arêtes. Cette condition permet de simplifier grandement le fonctionnement de l’algorithme. Il ne s’agit en fait que de placer les meilleures arêtes les unes après les autres, tant qu’elles ne créent pas de cycle. L’algorithme suivant représente les étapes nécessaires que fait l’algorithme de Kruskal, sans entrer dans la complexité temporelle des algorithmes d’UNION-FIND et de tri.L’algorithme de Kruskal se fait en deux phases. La première phase fait un tri des arêtes et la deuxième phase construit l’arbre couvrant minimal en plaçant les plus petites arêtes tant qu’elles ne créent pas de cycle. Le tri des arêtes prend un temps O(m lg m) pour un problème avec m arêtes. La boucle principale est exécutée dans le pire des cas m fois quand le graphe est creux (toutes les arêtes sont nécessaires pour faire le MST). Et nous avons également affaire au pire cas quand l’arête la plus coûteuse est nécessaire pour faire le MST. Cependant, dans un problème typique avec un graphe très dense, il faut s’attendre à ce que la boucle principale ne s’exécute qu’une fraction de fois car l’algorithme s’arrêtera avant. En effet, si une certaine condition est respectée, l’algorithme peut se terminer prématurément.

Algorithme de Prim

L’algorithme de Prim [Prim 1957] est un algorithme qui trouve l’arbre couvrant minimal d’une manière plus centralisée. En effet, à chaque itération de l’algorithme, l’élément le plus proche de l’arbre courant est ajouté. Si un graphe possède un nombre S de sommets, il faudra (S-1) itérations pour couvrir tous les sommets du graphe et obtenir l’arbre couvrant minimal.

L’algorithme de Prim a donc un fonctionnement très simple. L’ensemble de départ contient un sommet St∈S et à chaque itération la meilleure arête est choisie pour étendre notre ensemble de façon optimale. Dans le cas du problème du MST, nous choisissons la plus courte arête qui relie notre ensemble à un nouveau sommet.

Nous pouvons donc découper les différentes tâches de Prim comme suit :
1. Création de l’ensemble de départ.
2. Sélection de la meilleure arête à ajouter pour agrandir notre ensemble de départ.

L’étape 1 ne peut pas être optimisée. La création de l’ensemble de départ se fait toujours en temps constant en choisissant aléatoirement ou arbitrairement le sommet de départ. L’étape 2 doit être répétée (S-1) fois pour trouver toutes les arêtes du MST. En revanche, le processus de sélection peut être amélioré à l’aide d’une meilleure structure de données.

Algorithme de Prim avec une matrice de distances

La matrice d’adjacence est une structure de donnée assez générale pour représenter un graphe. Elle est définie comme suit : si la case ij de la matrice possède la valeur 1, cela veut dire qu’une arête existe entre le sommet i et le sommet;.
La matrice de distances inscrit la distance de l’arête dans la case ij. Par exemple, le chiffre 5 indique que l’arête a un poids de 5 alors qu’une valeur négative indique l’absence d’une arête. Dans un graphe très dense, chaque sommet possède une arête vers tous les autres sommets du graphe, ce qui nécessite donc une matrice de taille n2 pour représenter toutes les arêtes possibles.
L’algorithme de Prim avec une matrice de distances fonctionne en répétant deux opérations dans la boucle principale : l’ajustement des priorités et le choix du prochain sommet. L’ajustement des priorités se fait en itérant sur toute la ligne de la matrice correspondant au sommet courant. Pendant que cette ligne de matrice est visitée, un vecteur de priorités contenant la proximité de chaque sommet est ajusté.

Ensuite, le choix du prochain sommet se fait en itérant sur tout le vecteur de priorités ajusté précédemment et en choisissant l’arête la plus courte. À partir de cette arête, un nouveau sommet est atteint l’algorithme recommence l’ajustement des priorités.
L’algorithme se termine quand tous les sommets sont dans le MST, après n-1 étapes. Puisque les deux opérations ajustement et sélection fonctionnent respectivement en O(n) et que l’algorithme les répète n-1 fois, l’algorithme de Prim avec la matrice de distances a une complexité temporelle en O(n2).

Table des matières

INTRODUCTION GÉNÉRALE
CHAPITRE 1: ARBRE COUVRANT MINIMAL 
1.1 Introduction 
1.2 Graphes, Arbres et arbres couvrants 
1.3 Propriétés d’un arbre couvrant minimal 
1.4 Algorithmes d’UNION-FIND 
1.4.1 Méthode 1 : Tableau de correspondance entre un sommet et son groupe
1.4.2 Méthode 2 : Compression par chemin
1.5 Algorithme de Borûvka 
1.5.1 Exemple
1.6 Algorithme de Kruskal 
1.7 Algorithme de Prim 
1.8 Exemple étape par étape 
1.9 Algorithme de Prim avec une matrice de distance
1.10 Liste d’adjacence
CHAPITRE 2: LES FILES DE PRIORITÉ 
2.1 Introduction 
2.2 Liste chaînée 
2.3 Lestas 
2.3.1 Comparaison des opérations de base sur différents tas
2.3.2 Le tas binaire
2.3.3 Opération d’insertion
2.3.4 Suppression du minimum
2.3.5 Opération decreasekey
2.3.6 Opération delete
2.3.7 Construire le tas en temps linéaire
2.3.8 Exemple de construction d’un tas
2.3.9 Preuve de la borne
2.4 Le tas binomial 
2.4.1 Structure du nœud binomial
2.4.2 Trouver le minimum
2.4.3 Union de deux tas binomiaux
2.4.4 Union de deux arbres de degré k
2.4.5 Union rapide
2.4.6 Opération d’UNION
2.4.7 Opération DecreaseKey
2.4.8 Suppression du minimum
2.5 Tas de Fibonacci 
2.5.1 Opération de l’Union
2.5.2 Opération d’insertion
2.5.3 Extraction du minimum
2.5.4 Opération decreaseKey
CHAPITRE 3: COMPARAISON EMPIRIQUE DES PERFORMANCES 
3.1 Introduction 
3.2 Les programmes testés 
3.3 Mesures du temps 
3.4 Note sur l’algorithme de Borûvka et de Kruskal 
3.5 Résultats empiriques 
3.5.1 Graphes creux
3.5.2 Graphes moyennement denses
3.5.3 Graphes denses
3.6 Consommation mémoire 
3.7 Algorithmes de Union-Find pour Kruskal 
3.7.1 UNION-FIND sur les graphes creux
3.7.2 UNION-FIND sur les graphes moyennement denses
3.7.3 UNION-FIND sur les graphes denses
3.8 Discussion sur les résultat

Télécharger le rapport complet