Affinage de partition chez les graphes.
L'objectif de ce sujet est de présenter le paradigme d'affinage de partition en algorithmique avec des applications aux graphes (partition refinement en anglais). Contrairement à la problématique d'union/find où on part d'une partition très fine (en général les singletons) pour fusionner ensuite au fur et à mesure les parties (utilisé par exemple dans l'algorithme de Kruskal), il s'agit de partir d'une partition très grossière (en général l'ensemble de base en une seule partie) pour la subdiviser au fur et à mesure. Ce paradigme peu connu est pourtant très utile, notamment en algorithmique des graphes. On pourra travailler à partir de la thèse de Christophe Paul (depuis le chapitre 4, page 87) :
On pourra par exemple illustrer ce paradigme avec le calcul de sommets jumeaux, le tri lexicographique de chaines de caractères (meme si ce n'est pas tout à fait des graphes), le calcul de parcours Lex-BFS ou d'autres exemples tirés du manuscript ou d'articles que vous pouvez trouver utilisant cette technique.