Abstract FR:

De nouvelles approches du probleme de l'isomorphisme de deux graphes sont presentees: certaines particularites des elements propres des matrices d'adjacence sont montrees, la reformulation du probleme en termes d'optimisation d'une fonction pseudobooleenne d'une part et de recherche de courts vecteurs dans un treillis d'autre part est examinee. Dans presque tous les cas d'isomorphisme, et moyennant certaines conditions, l'algorithme de reduction de lenstra, lenstra et lovasz revele un court vecteur associe a une permutation solution. Il est montre d'autre part que la proportion des graphes ayant un groupe d'automorphisme non reduit a l'identite tend vers zero exponentiellement lorsque le nombre des sommets des graphes tend vers l'infini. Une conjecture est enfin posee selon laquelle presque toutes les instances du probleme d'isomorphisme de deux graphes ou l'isomorphisme est effectif peuvent etre reconnus en temps polynomial, la proportion des cas d'echec tendant exponentiellement vers zero lorsque le nombre des sommets des graphes consideres tend vers l'infini. Des resultats annexes, necessaires aux demonstrations, sont etablis relativement aux denombrement des points entiers dans les spheres de grandes dimensions