Graphes et sous graphes

Hello,

Voici mon problème:

Je dispose d'un ensemble de graphe non orientés, que je représente de deux facons: une liste de voisins connectés à chaque sommet (a chaque sommet correspond donc une liste de sommets connectés) , et la liste des arrètes (liste de couple de sommets donc).

Ce que j'aimerai faire, c'est a partir d'un sous graphe déterminé sur un des graphes connus, pouvoir retrouver ce sous graphe dans chacun des autres graphes (en d'autre termes, récupérer les sommets/connexions qui correspondent au sous graphe désiré).

L'application de mon problème peut se faire par exemple sur des molécules: on récupère un motif atomique donné (par exemple, 6 atomes formant un anneau), et on recherche ce type de squellette dans un ensemble d'autres molécules.

Quelqu'un sait-il si un algorithme existe déja pour faire ce genre de chose? J'ai pour le moment réfléchi un peu mais je n'ai pas encore trouvé de solution, n'étant pas spécialiste de l'algorithmique des graphes que je sais parfois trés complexe...

Merdi d'avance ;)

Ca s'appelle du "Subgraph Matching" et c'est un sujet très actif dans le petit monde de l'algorithmie.

Je te recommande la lecture de:

- Graph Indexing: A Frequent Structure*based Approach

et

- Algorithmics and Applications of Tree and Graph Searching

A+

Je sens que ca ne va pas être de la tarte :aie:

Merci en tout cas, je vais essayer de comprendre tout ca.
Si quelqu'un a d'autre pistes, un début d'idée ou d'algo, n'hésitez pas.