Discussion :

[Jean-Marc.Bourguet]

Bonjour,

Je cherche des algorithmes, des references et meme simplement des mots cles interessants pour le probleme de l'isomorphisme de graphe (je connais nauty) en general et plus precisement les variantes suivantes:
- recherche des differences entre deux graphes (avec une description "comprehensible" de celles-ci)
- recherche des occurences d'un "petit" graphe a l'interieur d'un grand
- recherche des occurences approximatives d'un petit graphe a l'interieur d'un grand
en particulier dans le cas ou les noeuds ont des annotations.

Merci.

[FrancisSourd]

La notion de distance d'édition entre les chaînes se généralisent naturellement aux graphes. On parle souvent de "graph completion" ou "graph deletion" lorsqu'il s'agit d'ajouter ou supprimer des arêtes. J'imagine que des chercheurs ont généralisé cela lorsqu'on ajoute ou supprime des noeuds.
Il s'agit alors de trouver le coût minimal pour passer d'un graphe à l'autre ou, étant donné un graphe initial, de calculer le coût minimal pour obtenir un graphe ayant certaines propriétés (du genre "coloriable en 6 couleurs").

Evidemment ces problèmes sont très compliqués puisque trouver une toute bête k-clique dans un graphe est NP-complet.

Est-ce que les petits graphes ont certaines propriétés ou sont-ils quelconques?

[Jean-Marc.Bourguet]

La notion de distance d'édition entre les chaînes se généralisent naturellement aux graphes. On parle souvent de "graph completion" ou "graph deletion" lorsqu'il s'agit d'ajouter ou supprimer des arêtes. J'imagine que des chercheurs ont généralisé cela lorsqu'on ajoute ou supprime des noeuds.
Il s'agit alors de trouver le coût minimal pour passer d'un graphe à l'autre ou, étant donné un graphe initial, de calculer le coût minimal pour obtenir un graphe ayant certaines propriétés (du genre "coloriable en 6 couleurs").

J'ai plusieurs cas de figures, qui jouent tous autour du meme probleme: etablir une correspondance entre deux graphes qui soit proche d'un iso-morphisme.

Le premier est l'isomorphisme.

Le deuxieme c'est un des graphes est incomplet.

Le troisieme c'est un des graphes a des erreurs (non seulement incomplet, mais en plus pas necessairement un sous-graphe).

En fait je ne sais pas a priori dans quel cas je suis entre les trois precedants.

Le quatrieme c'est un des graphes est nettement plus petit et il faut trouver les occurences.

Le cinquieme c'est un des graphes est nettement plus petit et il faut trouver les occurences approchantes.

Dans ce dernier cas j'ai une notion de distance qu'il serait bien de minimiser (et en fait on refuse les cas trop distants), mais elle est souple et je peux la modifier si j'ai de bons arguments pour cela.

Pour le moment, je fais deux recherches pour le 4ieme et le 5ieme cas, mais fusionner les deux avec un parametre cas trop distants pouvant etre place a 0
serait mieux.

Evidemment ces problèmes sont très compliqués puisque trouver une toute bête k-clique dans un graphe est NP-complet.

Je sais que le probleme de l'isomorphisme des graphes n'est pas connu pour etre NP-complet, mais il n'est pas connu non plus pour ne pas l'etre (du moins la derniere fois que j'ai fait un etat des lieux, il y a deux ou trois ans).

Est-ce que les petits graphes ont certaines propriétés ou sont-ils quelconques?

Relativement quelconques.

Les graphes sont bipartites, mais la derniere fois que j'ai regarde, ca n'avait pas l'air d'etre une propriete interessante pour ce genre de probleme. En tout cas j'avais rien trouve.

Le graphe dans lequel on fait la recherche n'est pas dense du tout (en general moins d'une dizaine d'arcs par noeuds meme si quelques un peuvent en avoir des milliers).
Et ce graphe peut etre gros (plusieurs millions de noeuds).

[FrancisSourd]

Je sais que le probleme de l'isomorphisme des graphes n'est pas connu pour etre NP-complet, mais il n'est pas connu non plus pour ne pas l'etre (du moins la derniere fois que j'ai fait un etat des lieux, il y a deux ou trois ans).

C'est effectivement le premier problème ouvert du Garey-Johnson. Wikipedia mentionne qu'il est toujours ouvert. Ma remarque concernait les problèmes de trouver au moins une occurence d'un sous-graphe.

J'ai trouvé ce lien mais comme il est assez ancien, tu dois le connaître
http://www.cs.ualberta.ca/TechReport.../TR96-20.ps.gz

Les deux-trois bouquins de graphes "avancés" que j'ai sous la main ne sont pas très loquaces sur ce problème...

En tout cas, je trouve que ce sont de très beaux problèmes...

[djo.mos]

Jette un coup d'oeil ici :
http://www710.univ-lyon1.fr/~csolnon...s/evocop05.pdf

C'est un document qui parle de differents types de problèmes d'appartiement de graphes et presente la solution de ses auteurs, qui est l'algorithme Ant-GM.
En espérant que ça t'aide.