Nombre de chemin hamiltonien avec des noeuds distingués
Par Arthur Milchior le mercredi 13 janvier 2010, 21:33 - Informatique - Lien permanent
Étrangement, cette liste de nombre ne semble pas se trouver dans l'encyclopédie de Sloane. Il est malheureusement impossible de proposer des suites actuellement, le temps que cela devienne un wiki, je vous propose donc les premières valeurs.
the number of hamiltonian graph of size 2 is 1
the number of hamiltonian graph of size 3 is 4
the number of hamiltonian graph of size 4 is 34
the number of hamiltonian graph of size 5 is 620
the number of hamiltonian graph of size 6 is 22906
the number of hamiltonian graph of size 7 is 1666987
Sachant que j'aurai un problème si il y a plus de 4294967295 graphes (la plus grande valeur des unsigned int)
L'algorithme est relativement simple: puisque chaque graphe hamiltonien possède possède un chemin de longueur N, pour toute permutation sigma de 0,N-1 je prend un graphe en mettant une arête entre sigma(i) et sigma(i+1) pour i<N-1. Ensuite, récursivement, pour toutes les arêtes, si elles ne sont pas dans le graphe, je les rajoutes ou non. Cela me donne nécessairement un graphe hamiltonien.
Bien sur un graphe qui a m chemins hamiltoniens sera généré m fois, donc pour éviter de compter plusieurs fois, je stocke tout les résultat dans une table de hashage. La table vérifiant l'égalité entre ses éléments, les graphes ne seront rajouté qu'une fois.
Le nombre de graphe hamiltonien sera donc le nombre d'élément de la table !
Cela nécessite d'énumérer toutes les permutations, ce qui semble se faire en O(n^(n+1))[1], et pour chacune des n! permutations, on génère tout en 2^O(n^2). Le temps de calcul est vraiment atroce ! Je suis donc encore à la recherche de moyen de l'améliorer. Par exemple, un algo pour les factoriel peut être exécuter en O(n n!) mais est plus dur et ne fournit pas un réel progrès.
Le code est ici compte.cpp, il doit être compilé avec -std=c0X car j'utilise des tables de hashage de la norme 0X. Il se compile sans problème avec g.
J'ai vérifié les 3 premières valeurs à la main, et elles sont bonnes, je suppose que mon algorithme est bon... Mine de rien, je suis sur ce code depuis dimanche (je n'ai pas fait que ça non plus).
Je mettrai les réponses suivante quand mon ordinateur me les auras craché. Pour le moment le calcul de la taille 8 ralentit trop mon ordinateur !
Note
[1] Je n'ai pas trouvé d'algorithme plus rapide, si quelqu'un connait, je suis preneur