Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

Le problème de l'arbre couvrant minimal est un des plus vieux problèmes en théorie des graphes. La problématique se pose comme suit : étant donné un graphe avec un nombre de sommets et un nombre d'arêtes ayant des poids de valeurs dans l'ensemble des entiers relatifs, l'arbre couvrant minimal consiste à trouver l'ensemble des arêtes permettant de rejoindre tous les sommets sans former de cycle, et ce, avec un coût minimal. Ce problème trouve des applications pratiques variées : il est directement applicable pour l'optimisation et la conception de divers types de réseaux (électrique, internet, etc.). Son application la plus populaire est actuellement dans le domaine du forage de données. La raison étant que certains algorithmes construisent l'arbre minimal en faisant grossir des groupes d'éléments progressivement. Ces groupes, appelés également clusters, représentent ensuite des groupes d'éléments similaires, ce qui permet de faire du forage de donnée efficacement. Il suffit au préalable de transformer les données multidimensionnelles du problème de clustering en graphe. Pour trouver l'arbre couvrant minimal, de nombreux algorithmes ont été proposés dans la littérature et ils sont pour la plupart assez performants. Cependant, avec l'invention récente de meilleures structures de données et de nouvelles techniques, les algorithmes n'ont cessé d'évoluer dans les vingt dernières années. Se pose donc la question : quel est l'algorithme le plus performant d'un point de vue théorique et/ou pratique? Les algorithmes testés dans ce mémoire ont des complexités temporelles assez semblables ; il est donc difficile de prévoir a priori celui qui sera le plus performant. Nous avons pour cela choisi une série d'algorithmes résolvant ce problème, nous avons expliqué en détail leur fonctionnement et nous les avons programmés en utilisant plusieurs structures de données. Ces algorithmes sont ceux de Kruskal, Borûvka et Prim. L'algorithme de Prim a été implémenté avec de nombreuses files de priorité et les algorithmes de Kruskal et Borûvka utilisent les meilleurs algorithmes de gestion des ensembles disjoints. Nous avons ensuite fait des tests empiriques sur des graphes de différentes tailles et densités afin de pouvoir confirmer les avantages de leur complexité temporelle. Les résultats obtenus permettent de tirer de nombreuses conclusions sur les performances de chaque algorithme en fonction de la densité du graphe. L'algorithme de Borûvka sort notamment du lot, car il propose des performances excellentes pour toutes les densités de graphe.