Bonjour,
C'est quoi la ou les différences entre les chaines (cycles) eulériennes et les chaines (cycles) hamiltoniennes?
Explications (2)
Explication d’élève
30 avril 2021
Bonjour CitrouilleSolidaire2466!
Merci de faire appel à nos services. 😉
Une chaine eulérienne est une chaine qui passe par toutes les arêtes d'un graphe connexe une seule fois.
Une chaine hamiltonienne est une chaine qui passe par tous les sommets d'un graphe connexe une seule fois.
Je te joins un lien provenant de notre site qui aborde les chaines et les cycles, si tu souhaites réviser ces notions:
N'hésite pas à nous réécrire!
Éveline :)
Explication d’élève
30 avril 2021
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!
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. :)
L’explication sera supprimée définitivement. Voulez-vous continuer?