Chemin hamiltonien

Chemin hamiltonien

Graphe hamiltonien

En théorie des graphes, 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 est alors appelé cycle hamiltonien. Un graphe hamiltonien ne doit pas être confondu avec un graphe eulérien.

Le plus petit graphe hamiltonien à n sommets est le graphe cycle Cn. Mais un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens. Ainsi le graphe de Chvátal a 12 sommets, 24 arêtes et 370 cycles hamiltoniens distincts[1].

Trouver un cycle hamiltonien pour un graphe donné est un problème difficile sur le plan algorithmique, c'est-à-dire de type NP-complet. Le problème du voyageur de commerce s'apparente d'ailleurs à la recherche d'un cycle hamiltonien en ajoutant une contrainte : la minimalisation de son poids dans un graphe complet dont les arêtes sont pondérées.

Sommaire

Chemin hamiltonien

Les chemins hamiltoniens sont dus à William Rowan Hamilton qui était astronome royal en Irlande, au milieu du XIXe siècle. Dans un graphe, on qualifie d’hamiltonien un chemin qui passe une et une seule fois par chaque sommet du graphe. Un graphe possédant un cycle hamiltonien possède nécessairement un chemin hamiltonien, obtenu en enlevant une arête quelconque du cycle, mais la réciproque est fausse. Le problème du chemin Hamiltonien est aussi difficile que celui du cycle hamiltonien, puisqu'ils sont tous les deux NP-complets.

Un chemin hamiltonien dans un graphe est un chemin qui passe par tous les sommets une fois et une seule[2].

Recherche d'un chemin hamiltonien par ordinateur à ADN

D'après les recherches de Leonard Adleman, ce problème pourrait être soluble efficacement (au moins en pratique) par un ordinateur à ADN. Il serait alors suffisamment complexe et significatif pour constituer une preuve indubitable de l’intérêt de ces nouvelles machines. L'idée est de représenter les arêtes du graphes par des séquences d'ADN qui peuvent s'assembler linéairement quand elles ont une extrêmité commune. Un polymère formé par ces séquences correspond donc à un chemin.

L'algorithme proposé par Adleman est le suivant:

  1. Générer un grand nombre de séquences, correspondant à des chemins aléatoires
  2. Filtrer (par exemple par la masse) pour ne garder que les chemins avec n sommets (où n est la taille du graphe)
  3. Filtrer pour ne garder que les chemins qui contiennent une fois chaque sommet
  4. S'il reste des séquences qui passent les deux filtres, le graphe a un chemin hamiltonien.

Bibliographie

  • (en) Leonard Adleman, "An Abstract Theory of Computer Viruses", Springer-Verlag New York, Inc., 1990, ISBN 0-387-97196-3
  • (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 2-7011-4032-3
  • (fr) Jean-Baptiste Waldner, "Nano-informatique et intelligence ambiante - Inventer l'ordinateur du XXIe siècle", Hermes Science, London, 2006, ISBN 2-7462-1516-0

Références

  1. ↑ (en) Weisstein, Eric W [ttp://mathworld.wolfram.com/ChvatalGraph.html "Chvátal Graph" From MathWorld--A Wolfram Web Resource]
  2. ↑ Adapté de Nanoinformatique et intelligence ambiante - Inventer l'ordinateur du XXIe siècle Jean-Baptiste Waldner, Hermès Science, London, 2007 (avec la permission de l'auteur)

Liens externes

  • Portail des mathématiques Portail des mathématiques
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Graphe hamiltonien ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Chemin hamiltonien de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Chemin eulérien — Graphe eulérien En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété… …   Wikipédia en Français

  • Cycle hamiltonien — Graphe hamiltonien En théorie des graphes, 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 est alors appelé cycle hamiltonien. Un graphe hamiltonien ne… …   Wikipédia en Français

  • Graphe Hamiltonien — En théorie des graphes, 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 est alors appelé cycle hamiltonien. Un graphe hamiltonien ne doit pas être… …   Wikipédia en Français

  • Graphe hamiltonien — En théorie des graphes, 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 est alors appelé cycle hamiltonien. Un graphe hamiltonien ne doit pas être… …   Wikipédia en Français

  • Integrale de chemin — Intégrale de chemin Une intégrale de chemin («path integral» en anglais) est une intégrale fonctionnelle, c est à dire que l intégrant est une fonctionnelle et que la somme est prise sur des fonctions, et non sur des nombres réels (ou complexes)… …   Wikipédia en Français

  • Intégrale De Chemin — Une intégrale de chemin («path integral» en anglais) est une intégrale fonctionnelle, c est à dire que l intégrant est une fonctionnelle et que la somme est prise sur des fonctions, et non sur des nombres réels (ou complexes) comme pour les… …   Wikipédia en Français

  • Intégrale de chemin — Une intégrale de chemin (« path integral » en anglais) est une intégrale fonctionnelle, c est à dire que l intégrant est une fonctionnelle et que la somme est prise sur des fonctions, et non sur des nombres réels (ou complexes) comme… …   Wikipédia en Français

  • GRAPHES (THÉORIE DES) — On appelle théorie des graphes une classe de problèmes plus ou moins bien résolus. Leur résolution suscite chez les mathématiciens, en particulier à l’étranger, un engouement sans cesse croissant. Claude Berge, dans le discours inaugural des… …   Encyclopédie Universelle

  • Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe De Coxeter — Le graphe de Coxeter Nombre de sommets 28 Nombre d arêtes 42 Distribution des degrés 3 régulier Diamètre 4 Propriétés Hypohamilton …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”