Isomorphismes d'arbres et de graphes.

L'isomorphisme de graphes orientés ou non orientés est un problème très important de théorie des graphes, qui est susceptible d'intervenir dans de nombreuses applications. Parmi elles, on peut citer les requètes de recherche dans des bases de données dont les entrées sont des graphes (par exemple des molécules en chimie, des graphes conceptuels en représentation des connaissances, des circuits électroniques ...).

Tester si deux graphes sont isomorphes est clairement dans NP. Par contre on a encore beaucoup de mal à classer ce problème. Par exemple, on ne sait pas s'il est  NP-complet. Si bien qu'une classe de complexité a même été créée : celle des problèmes équivalent à l'isomorphisme de graphes (classe GI). Luks et Zemlyachenko (1983) ont décrit un algorithme dont la complexité en temps est O(e√(cn.log(n)))n est le nombre de sommet et c est une constante. Apparemment c'est la meilleure borne connue à ce jour.

L'objectif ici est de montrer qu'il existe des classes de graphes pour lesquelles le test d'isomorphisme est polynomial, en particulier la classe des arbres.  Les questions qui suivent donnent des pistes pour votre travail :

Quelques références (pas exhaustif).

Retour à la page des sujets.