Secondary V • 1d
bonjour j’aimerais savoir Dans le graphe ci-contre, trouve une chaîne simple de longueur 3, une chaîne eulérienne et une chaîne hamiltonienne
bonjour j’aimerais savoir Dans le graphe ci-contre, trouve une chaîne simple de longueur 3, une chaîne eulérienne et une chaîne hamiltonienne
Bon matin ChevreuilKappa7694 😊
Merci pour ta question!
Chaîne simple de longueur 3:
La longueur est toujours égale au nombre de sommets de la chaîne -1. Ainsi, il nous faudra 4 sommets. Cependant, comme on mentionne que cette chaîne doit être simple, elle ne doit donc pas passer deux fois par la même arête. Dans notre graphe, on peut donc dire que C-B-D-E est une chaine simple de longueur 3 (4 sommets et ne passe pas 2x par la même arête).
Chaîne eulérienne:
Une chaîne eulérienne est une chaîne qui parcourt toutes les arêtes d’un graphe connexe une et une seule fois. Ainsi, dans ton graphe, on pourrait prendre la chaîne E-D-B-C-A-F-D-A.
Chaîne hamiltonienne:
Une chaine hamiltonienne est une chaine qui passe par tous les sommets d’un graphe connexe une et une seule fois. Ainsi, tu pourrais prendre la chaîne suivante: E-D-B-C-A-F. Tu passe donc par tous les sommets une et une seule fois.
Voici une fiche sur les différentes chaînes et cycles qui pourrait t'intéresser:
Si jamais tu as d'autres questions, n'hésite surtout pas ✨
Je te souhaite une merveilleuse journée!
Mélodie 🎶