Partindo do famoso problema das sete pontes de Königsberg temos estado a analisar os grafos pela importância das suas arestas e dos percursos sobre estas.
    Mas também podemos nos concentrar sobre os seus vértices, pelo número de visitas a estes vértices.
    Repare-se que, nesta nova abordagem, embora também se trate de procurar circuitos sobre grafos, o problema não está em percorrer todas as ruas existentes sem repetições ou com o mínimo de repetições, mas antes em escolher algumas delas (quem sabe as mais curtas) para visitar todos os pontos de interesse, sem ter de repetir a visita a qualquer um deles.
    As anteriores situações referiam-se a redes viárias, de estradas ou de ruas - redes de arestas. Sobre estas novas situações podemos referi-las a redes de cidades, de pontos de interesse, de pontos a visitar - redes de vértices ou de nós.
 Circuitos de Hamilton
    Um giro ou uma volta que começa e acaba num vertex de um grafo e passa por cada vertex uma e uma só vez, chama-se circuito de Hamilton.
 
 

Nota:
Nos circuitos de Hamilton não é necessário percorrer todas as arestas do grafo, o nosso interesse são os vértices.
 

«» Exemplo de dois grafos que não admitem Circuito de Hamilton:

 

«» Segue-se o exemplo de um grafo que admite Circuito de Hamilton: um circuito poderá ser AHGFEDIBCA:

Reparemos que a figura anterior foi obtida da figura (b) acrescentando uma aresta, a aresta CA.
 


MÁS NOTICIAS:
É muito mais difícil determinar quais são os grafos conexos que admitem circuitos hamiltonianos do que determinar quais admitem circuitos de Euler.
Contrariamente ao que se passou com os circuitos de Euler não há um método assim tão simples para nos informar sobre a existência ou não de circuito hamiltonianos para um determinado grafo.
Algumas classes de grafos são conhecidas como tendo circuitos de Hamilton, e algumas classes especiais de grafos são conhecidas por não os admitirem.
Infelizmente, não conheçemos  um método para determinar se um grafo qualquer tem ou não tem um circuito hamiltoniano. AGUARDEMOS PELO FUTURO !!!
Consulte o problema do
                                                    ---»  CAIXEIRO VIAJANTE QUE TEM DE VISITAR SEIS CIDADES IBÉRICAS
 
 
 
 
Voltar à página principal