[grafos] hamiltoniano

[Jose Coelho de Pina <coelho@linux.ime.usp.br>]

Salve,

Alguém ai andou brincando com o programa hamiltoniano 
que em ~coelho/grafos/sgb/exemplos/  ?

Um grafo que possui um circuito que passa por cada um de
seus vértices é chamado de hamiltoniano. O programa
hamiltoniano decide se um grafo dado é ou não hamiltoniano. 

Gostaria de saber quanto tempo o programa demora para
(digamos) verificar se um grafo pseudo-aleatório com 16
vértices é Hamiltoniano. E um grafo com 32 vértices?  E um
grafo com 64 vértices? Variem também o número de arcos do
grafo.  O que você notaram ao fazer este pequeno
experimento?

coelho

P.S. Lembrem-se que para cronometrar o tempo gasto basta 
     fazer:

 meu_prompt>time hamiltoniano -r -n16 -m32 
 grafo: random_graph(16,32,0,0,1,0,0,1,1,0).
 numero de vertices: 16.
 numero de arcos: 32.
 Vertice origem: 6.
 Grau de saida: 0.
 O grafo nao e hamiltoniano.
 no backtrackings: 0.
 no nos gerados: 0.

 real    0m0.134s
 user    0m0.020s
 sys     0m0.000s