Comme la question posée sur l'image dans le lien.Y at-il un circuit hamiltonien dans le graphique dans le lien ci-dessous?
Y at-il un hamilton circuit dans le graphique ci-dessus?
J'ai trouvé quelques hamilton path comme:
c - b - a -j - i - h - f - e - d - g
Mais hamilton circuit
Je ne peux pas ajouter l'image ici depuis stackoverflow na pas me permettre
Il ne peut pas être un hamiltonien cycle.
Preuve:
Dans un cycle hamiltonien, chaque sommet doit être visité et pas de bord peut être utilisé deux fois. Ainsi, si un sommet a le degré deux, ses deux bords doivent être utilisés dans un tel cycle.
a, c et g sont deux degrés, donc il suit que s'il y a un cycle hamiltonien il doit contenir le chemin j - a - b - c - d - g - h. Toutefois, ce chemin ne contient pas e mais il contient deux des voisins de e, b et d. e a seulement un voisin restant, f, donc il n'y a aucun moyen d'étendre le chemin à un cycle hamiltonien qui contient e. Ainsi, il ne peut y avoir de cycle hamiltonien dans le graphique.
wow telle explication de détail XD gentille maintenant je comprends – nff21
Etes-vous en train d'écrire un programme pour trouver les circuits? Si oui, incluez ce que vous avez essayé jusqu'à présent. Sinon, c'est probablement hors sujet. – blm
l'éditer XD thx pour l'avis – nff21