nombre de cycle hamiltonien

[invite3ee7059b]

Bjr, est ce que quelqu'un peut m'aider pour repondre à cette question !
Combien de cycles hamiltoniens possède le graphe Kn?
merci
-----

[invite986312212]

ça doit être (n-1)! puisque chaque ordonnancement des n sommets correspond à un cycle hamiltonien unique au choix du point de départ près.

[Amanuensis]

Extrait du Wiki anglophone, consulté pour avoir le sens précis de l'expression "cycle hamiltonien" :

Number of different Hamiltonian cycles for a complete graph = (n-1)! / 2.

La direction de parcours ne distingue pas deux cycles...

[Amanuensis]

Je précise, puisque la question ne le fait pas totalement (au cas où Kn serait employée aussi pour un graphe orienté), que la réponse que j'ai donnée est pour un graphe non-orienté.

[A voir en vidéo sur Futura]