Un
graphe hamiltonien est un graphe possèdant au moins un cycle passant par tous les sommets une et une seule fois. Un tel cycle élémentaire - ne passant pas deux fois par le même sommet - est alors appelé cycle hamiltonien. Un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens.
Trouver un cycle hamiltonien pour un graphe donné est un problème difficile sur le plan algorithmique - de type NP-complet -, relié au problème du voyageur de commerce - recherche d'un cycle hamiltonien de poids minimal dans un Graphe complet dont les arêtes sont pondérées.
Un graphe hamiltonien ne doit pas être confondu avec un Graphe eulérien.
Description du problème du chemin hamiltonien
Les chemins hamiltoniens sont dus à William Rowan Hamilton qui était astronome royal en Irlande, au milieu du XIX
e siècle. On qualifie d’hamiltonien un chemin qui passe une et une seule fois par chaque sommet du graphe qui lui sert de support comme le montre le schéma ci-contre.
C’est un problème largement étudié qui ne connaît pas vraiment d'algorithme efficace à ce jour.
Le temps de résolution croit de manière exponentielle au fur et à mesure que le nombre de sommets augmente.
Adelman, qui a largement étudié ce type de problème dans ses applications à l'ordinateur à ADN, disait : « On connaît des graphes de moins de 100 sommets pour lesquels, même en utilisant le meilleur algorithme et le meilleur ordinateur, la résolution du problème du chemin hamiltonien prendrait des centaines d’années. »
Au début des années 1970, les informaticiens ont démontré que ce problème était NP-complet : la plupart pense que l’on ne trouvera jamais d’algorithmes rapides pour ce type de problème bien que la preuve de cette supposition reste à fournir. Ce n’est pas un problème insoluble, mais le temps de calcul est excessivement long. Voici les cinq grandes étapes d’un algorithme permettant de résoudre ce type de problème :
- Générer un ensemble de chemins aléatoires ;
- Garder seulement les chemins qui commencent et se terminent respectivement par la ville de départ et celle d’arrivée ;
- Si le graphe possède n sommets, garder seulement les chemins qui ont exactement n sommets ;
- Garder seulement les chemins qui possèdent tous les sommets du graphe ;
- S’il reste un chemin, celui-ci est une solution.
Pour cette expérience, Leonard Adleman a cherché un problème suffisamment simple afin qu’un prototype d’ordinateur à ADN puisse le résoudre, mais suffisamment complexe et significatif pour constituer une preuve indubitable de l’intérêt de ces nouvelles machines.
Bibliographie
- (en) Leonard Adleman, "An Abstract Theory of Computer Viruses", Springer-Verlag New York, Inc., 1990, ISBN 0387971963
- (en) Leonard Adleman, "Towards a (MATH)ematical theory of self-assembly. Technical Report 00-722", Department of Computer Science, University of Southern California, 2000, ISBN 2701140323
- (fr) Jean-Baptiste Waldner, "Nano-informatique et intelligence quantique - Inventer l'ordinateur du XXIe siècle", Hermes Science, London, 2006, ISBN 2746215160
Liens externes