J'ai des graphes planaires cubiques relativement petits (40-80 nœuds) (3-réguliers), et je dois décider de leur hamiltonicité. Je suis conscient du fait que cette tâche est NP-complet, mais je l'espère pour les algorithmes de temps asymptotiquement exponentielles qui sont néanmoins très rapide pour la taille du graphique Je suis intéressé parTrouver des cycles hamiltoniens dans des graphes planaires cubiques
40 nœuds semble faisable. Vous choisissez 40 des 60 arêtes à inclure.
Essayons d'abord une recherche en profondeur. Pour commencer, choisissez un sommet V. Vous devrez exclure exactement l'un de ses 3 arêtes incidentes. Essayez ces 3 possibilités une à la fois. Lorsque vous choisissez un contour à exclure, vous forcez l'inclusion de 4 arêtes. Après cela, nous appellerons les sommets du bord exclu "utilisé".
Si vous pouviez répéter ce processus 10 fois, vous auriez choisi les 40 arêtes, en recherchant seulement 3^10 (59049) possibilités. Bien sûr, vous manquerez de sommets "isolés" une fois que suffisamment d'arêtes auront été déterminées. Mais, nous avons maintenant une idée pour un algorithme. A chaque étape, essayez de choisir un sommet avec le moins de voisins "utilisés". En fait, il est préférable de choisir un sommet avec 2 voisins utilisés, car le bord utilisé est forcé. Je ne suis pas sûr si choisir un sommet avec 1 ou 0 voisins utilisés est le meilleur. Essayez les deux façons! (Et 3 voisins utilisés indiquent une recherche échouée)
Lorsque nous avons fini de sélectionner les arêtes, vérifiez qu'elles ne forment qu'un seul cycle.
Avez-vous quelques exemples de graphiques? Je pourrais essayer une implémentation simple.
de http://mathworld.wolfram.com/HamiltonianCycle.html. « Rubin (1974) décrit une procédure de recherche efficace qui peut trouver une partie ou la totalité des chemins et des circuits de Hamilton dans un graphique en utilisant des déductions qui réduisent considérablement les retours en arrière et les devinettes.
Le papier est en vente ici: http://portal.acm.org/citation.cfm?id=321850.321854