CAMINHOS HAMILTONIANOS
Sir William Rowan Hamilton foi um matemático, astrônomo e físico irlandês que trabalhou com teoria dos grafos no século XIX.
Um caminho em um grafo que passa por cada vértice exatamente uma vez é chamado um caminho Hamiltoniano. Não precisa passar por todas as arestas do grafo, mas deve cobrir todos os vértices sem repetição.
Você pode pensar num caminho Hamiltoniano como se fosse um passeio visitando cada vértice uma única vez.
Nem todos os grafos têm caminhos Hamiltonianos, e determinar se um grafo específico possui um pode ser um problema computacional desafiador.
O jogo “Icosiano” foi inventado também por Hamilton. Repare que o tabuleiro é a planificação das arestas e vértices de um dodecaedro regular (poliedro com doze faces, todas pentagonais).
Neste tabuleiro, podemos propor vários desafios, indo dos fáceis aos impossíveis!
Um dos primeiros desafios é achar um caminho passando exatamente uma vez em cada ponto. Esse tipo de caminho em grafos ficou conhecido como um caminho hamiltoniano. O caminho é chamado de circuito se volta ao ponto inicial. Nos caminhos eulerianos (vide as Pontes de Königsberg), passa-se exatamente uma vez em cada aresta.
Imagem: Alisson Ricardo.
Já para os próximos, ache um caminho hamiltoniano, ou seja, como os pinos enumerados, crie um caminho que passe uma unica vez por cada vértice. Pode criar um ciclo hamiltoniano? Isto é, um caminho no qual o último vértice seja adjacente ao primeiro?
Tente fazer as duas coisas anteriores em cada um dos dois
tabuleiros
Você nota aluma diferença essencial entre eles?
Agora bloqueie um dos vértices como se ele não existisse mais no grado. Você ainda consegue encontrar um caminho hamiltoniano? E um ciclo?
Você também pode bloquear dois ou mais vértices de uma vez só.
Entre todos esses desafios, você pode encontrar situações que não têm nenhuma solução possível!
