Zone d’entraide

CitrouilleSolidaire2466

Bonjour,

C'est quoi la ou les différences entre les chaines (cycles) eulériennes et les chaines (cycles) hamiltoniennes?

Andréa C

Salut!

D'abord, il ne faut pas confondre les chaînes avec les cycles!

Une chaine eulérienne est une chaine qui parcourt toutes les arêtes d’un graphe connexe une et une seule fois.

Lorsque la chaine eulérienne est fermée, on l’appellera cycle eulérien. C’est donc une chaine qui passe par toutes les arêtes et qui revient à son point de départ.

-------

Une chaine ou cycle hamiltonien(ne) est une chaine ou un cycle qui passe par tous les sommets d’un graphe connexe une et une seule fois. Les chaines hamiltoniennes sont fréquemment utilisées pour résoudre des problèmes d’optimisation (par exemple, trouver le chemin le plus court. Le problème du voyageur en est un bon exemple, voir la référence plus bas).

Ainsi, la différence entre une chaine ou un cycle eulérien et une chaîne ou un cycle hamiltonien est que l'eulérien est caractérisé par son passage par les arrêtes, alors que l'hamiltonien passe par les sommets!

Ce contenu est protégé par le droit d'auteur. Toute reproduction à l'extérieur des forums Alloprof est interdite et pourra être considérée comme une violation du droit d'auteur.

Je t'invite à consulter la fiche des chaînes et des cycles afin de t'assurer de bien comprendre chacun pour ensuite te permettre de les comparer. :)