Secondaire 5 • 4a
Bonjour,
C'est quoi la ou les différences entre les chaines (cycles) eulériennes et les chaines (cycles) hamiltoniennes?
Bonjour,
C'est quoi la ou les différences entre les chaines (cycles) eulériennes et les chaines (cycles) hamiltoniennes?
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.
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. :)
Explication d'Alloprof
Cette explication a été donnée par un membre de l'équipe d'Alloprof.
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 :)
Suggestions en lien avec la question
Suggestion en lien avec la question
Voici ce qui a été trouvé automatiquement sur le site, en espérant que ça t’aide!