Ho grafici planari cubici (3-regolari) relativamente piccoli (40-80 nodi) e devo decidere la loro Hamiltonicità. Sono consapevole del fatto che questo compito è NP-completo, ma spero per gli algoritmi di tempo asintoticamente esponenziali che sono comunque molto veloce per le dimensioni del grafico Sono interessato aRicerca di cicli hamiltoniani nei grafici planari cubici
40 nodi sembra fattibile. Hai scelto 40 di 60 spigoli da includere.
Proviamo una ricerca in profondità.
Per iniziare, selezionare un vertice V. È necessario escludere esattamente uno dei suoi 3 bordi incidenti. Prova queste 3 possibilità una alla volta. Quando scegli uno spigolo da escludere, stai forzando l'inclusione di 4 spigoli. Dopodiché chiameremo i vertici del margine escluso "usato".
Se si potesse ripetere questa procedura 10 volte, avresti scelto tutti i 40 bordi, cercando solo 3^10 (59049) possibilità. Naturalmente, finirai con i vertici "isolati" dopo aver determinato un numero sufficiente di bordi.
Ma ora abbiamo un'idea per un algoritmo. Ad ogni passo, prova a scegliere un vertice con il minor numero di vicini "usati". In realtà, scegliere un vertice con 2 vicini usati è la cosa migliore, poiché il margine utilizzato è forzato. Non sono sicuro che scegliere un vertice con 1 o 0 vicini usati sia il migliore. Prova in entrambe le direzioni! (E 3 vicini usati indicano una ricerca fallita)
Quando abbiamo finito di raccogliere i bordi, controlla se formano un singolo ciclo.
Avete alcuni grafici di esempio? Potrei provare una semplice implementazione.
da http://mathworld.wolfram.com/HamiltonianCycle.html:. "Rubin (1974) descrive una procedura di ricerca efficiente che può trovare alcuni o tutti i percorsi e i circuiti di Hamilton in un grafico utilizzando deduzioni che riducono notevolmente il backtracking e le congetture ".
la carta è in vendita qui: http://portal.acm.org/citation.cfm?id=321850.321854