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))}) où 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 :

• Décrire précisément au moins un algorithme polynomial pour tester l'isomorphisme entre deux arbres enracinés qui sont orientés naturellement à partir de leurs racines.
  
• Donner au moins un algorithme polynomial pour tester l'isomorphisme de deux arbres non enracinés, non orientés.
• Est-ce que l'isomorphisme est polynomial pour la classe des cographes ?
• Une variante du problème d'isomorphisme est le problème de plongement : étant donnés G₁ et G₂ deux graphes, G₁ se plonge dans G₂ si G₁ est isomorphe à un sous-graphe de G₂. Si G₁ et G₂ sont deux graphes non orientés quelconques, quelle est la complexité du problème ? Et si G₁ et G₂ sont des arbres enracinés (subtree isomorphism en anglais) ?
  

Quelques références (pas exhaustif).

• The design and analysis of computer algorithms, livre de Aho, Hopcroft et Ullman, Addison-Wesley (1974). Des informations sur le problème ...
• Algorithms on trees and graphes, livre de G. Valiente, Springer (2002). D'autres informations ... éventuellement à comparer avec ce qui est donné dans le Aho, Hopcroft, Ullman. Une remarque : les arbres enracinés dont on parle dans le sujet sont appelés "unordered trees" dans ce livre (les "ordered trees" étant encore autre chose).
  

Retour à la page des sujets.