L'auto-stabilisation, introduite en informatique par Dijkstra en 1973, est une technique qui permet de concevoir des systèmes distribués robustes tolérants aux défaillances. Un système distribué auto-stabilisant peut retrouver automatiquement un comportement correct après une défaillance d'un ou de plusieurs éléments dans le système. Comme le retour à un comportement normal doit se produire dans un temps fini et sans intervention extérieure, l'auto-stabilisation est un modèle algorithmique adapté à la
conception et au fonctionnement des systèmes distribués.

L'étude structurelle des graphes a été longuement travaillée par les chercheurs de ce domaine. De nombreux résultats (combinatoires et algorithmiques) sont connus pour construire, détecter, faire émerger des propriétés structurelles dans les graphes. Ces outils puissants ne sont connus malheureusement que dans leurs versions séquentielles et centralisées, ce qui limite leur portée notamment envers les systèmes distribuées, dynamiques ou mobiles.

Cette thèse veut pallier à cette limite en s'intéressant à une étude structurelle des graphes dans sa version distribuée et dynamique. L'objectif est d'étudier la décomposition de graphes et la recherche de motifs spécifiques dans des graphes avec une algorithmie distribuée et auto-stabilisante. La portabilité de ces résultats théoriques sur des systèmes distribués autonomes à l'aide de cette algorithmie devient naturelle et utile pour le développement de protocoles efficaces et d'applications portables.