Cette thèse définit une famille de distances entre classes d'isomorphisme de graphes au moyen d'une construction originale.

Une deuxième partie propose un vaste tour d'horizon des propriétés de cette famille de distances : le Théorème 2.2 fournit un outil, utilisé tout au long de cette thèse, pour déterminer sous certaines conditions la valeur de la distance entre deux graphes. Les Théorèmes 2.11 et suivants décrivent la forme du graphe de distance associé à une distance.

Le Théorème 2.24 établit d'importants liens avec des distances étudiées par d'autres auteurs, et le Théorème 2.46 démontre la NP-complétude du problème de décision associé à notre famille de distances.

La dernière partie étudie différents algorithmes donnant une valeur approchée de la valeur de la distance entre deux graphes, dont la marche aléatoire, l'algorithme glouton, le recuit-simulé, la méthode tabou et les algorithmes génétiques. De nombreuses illustrations de leurs performances relatives, par des calculs en machine, justifient des directives d'utilisation.