Quelqu'un peut-il expliquer comment trouver le nombre de cycles hamiltoniens dans un graphique non dirigé complet?
Wikipedia dit que la formule est (N-1)! / 2 , mais lorsque j'ai calculé à l'aide de cette formule, K3 n'a qu'un seul cycle et K4 a été mon calcul incorrect?
3 Réponses :
Étant donné que le graphique est terminé, toute permutation commençant par un sommet fixe donne un cycle (presque) unique (le dernier sommet de la permutation aura un bord au premier sommet fixe. Sauf une chose: si vous visitez. Les sommets du cycle dans l'ordre inverse, c'est donc vraiment le même cycle (à cause de cela, le nombre est la moitié de ce que les permutations de sommets (N-1) vous donneraient).
E.g. Pour les sommets 1,2,3, fixez "1" et vous avez:
123 132
mais 123 inversé (321) est une rotation de (132), car 32 est 22 inverse.
Il y a (N-1)! Les permutations des sommets non fixes et la moitié de ceux-ci sont l'inverse d'un autre, il y a donc (N-1)! / 2 cycles hamiltoniens distincts dans le graphique complet de n sommets.
J'ai posé cette question à ces questions sur une question de Jam de Code de l'année dernière. Mais je ne suis toujours pas capable de comprendre l'algorithme peut vous expliquer cette question de la confiture de code code.google.com/codejam/contest/dashboard?c=32004#s=p2
Je générerais toutes les permutations de 2 ... n où 2 viennent dans la première moitié et sauvant ceux qui donnent l'un des bords interdits, c'est-à-dire si vos permutations sont 4235 (ce qui signifie le cycle 142351 ...) puis sauter SI 14 42 23 35 ou 51 sont interdits. Vous pouvez le faire car vous générez les permutations par ex. Si 14 était interdit, alors vous auriez arrêté à "4 ..."
Mais si le nombre de sommets est très grand, disons 30, puis générant toutes les permutations, 29! / 2 est calculellement très coûteux
Une dernière chose pourquoi as-tu dit "où 2 vient dans la première moitié"? Qu'est-ce que ça veut dire?
Eh bien, je voulais juste un moyen de distinguer la permutation P de l'inverse (P). Une façon de le faire est de choisir un élément (j'ai choisi 2) et de veiller à ce qu'il se produise dans la première moitié.
Vous avez raison que ma suggestion d'un graphique de 30 ou 300 noeuds est irréalisable. Cela semble être un problème délicat. Saviez-vous que vous pouvez télécharger le code source des gens qui l'a résolue?
Tous les sommets non adjacents à l'un des bords de 0 à 15 interdits sont indiscernables, il n'est donc pas nécessaire de générer des permutations de ces sommets indiscernables. Juste en utilisant ce fait devrait le rendre traitable.
Je pense que lorsque nous avons un cycle hamiltonien depuis chaque sommet réside dans le cycle hamiltonien si nous considérons un sommet comme cycle de départ et de fin. Nous devrions utiliser 2 bords de ce sommet.So que nous avons (N-1) (N-2) / 2 cycle hamiltonien, car nous devrions sélectionner 2 bords des bords N-1 qui sont liés à ce sommet.
Vous avez fait une erreur lorsque vous avez calculé le nombre total de cycles. Un cycle hamiltonien doit inclure tous les bords.
k4 n'a que 3 cycles de ce type et au total, il dispose de 5 cycles, la formule est donc correcte.Anubhav est incorrect, un cycle hamiltonien n'a pas besoin d'inclure tous les bords, il doit inclure tous les nœuds / sommets.