redes de cidades
& circuitos de Hamilton (9)

 

No caso dos circuitos de Euler, o nosso problema consistia em encontrar caminhos, a começar e a acabar no mesmo vértice, que passassem por todas as arestas e apenas uma vez por cada uma delas. Mas podíamos visitar os vértices tantas vezes quantas quiséssemos. O que acontece se trocarmos os papeis das arestas e dos vértices?

Terá interesse procurar num grafo caminhos que passem por todos os vértices sem repetirmos qualquer deles, mas sem nos preocuparmos em passarmos por todas as arestas?

De facto, este problema tem grande interesse para todos os circuitos de distribuição. Cerca de 1857, Hamilton apresentava um problema comercial interessante. O modelo consistia num dodecaedro (de madeira) em que cada um dos vinte vértices representava uma cidade, e o problema consistia em encontrar um caminho de arestas que começasse e acabasse no mesmo vértice e sem repetir a visita a qualquer dos vértices intermédios.

Uma das soluções apresentadas, pode ver-se na figura:

Num dado grafo G=(V, A), chama-se circuito de Hamilton (ou hamiltoniano) a um caminho que começa e acaba num mesmo vértice, passando por todos os vértices e não mais do que uma vez por cada um deles. Quando um grafo admite um circuito hamiltoniano, chamamos-lhe grafo hamiltoninano.

Apesar da reciprocidade das propriedades eulerianas e hamiltonianas, não há um algoritmo eficiente para determinar se um grafo é hamiltoniano. Não nos vamos debruçar sobre as subtilezas do problema, mas vale a pena referir o interesse das relações que podem ser estabelecidas com os sólidos regulares. Um grafo é definido abstractamente pelos seus vértices e arestas e, embora tenhamos até agora, trabalhado com grafos na folha de papel (ou no monitor) sem nos preocuparmos se eles representam percursos no espaço. De facto, podemos falar de grafos planares e não planares com um sentido bem preciso: Diremos que são planares os grafos cujas arestas só se intersectam nos vértices e não planares aqueles cujas arestas se intersectam noutros pontos que não os vértices. Kuratowski demonstrou que um gafo é planar quando não contem qualquer subgrafo da forma

É claro que, do ponto de vista da teoria dos grafos, os dois grafos da figura seguinte são o mesmo (a menos de um isomorfismo, como se diz em Matemática: correspondência um a um entre vértices e arestas, sendo que A é correspondente de A', H é correspondente de H' e a aresta AH é correspondente da aresta A'H', )

E que sendo assim não diríamos que o grafo da esquerda da figura é não planar, se podemos desenhar um equivalente que é planar. Se isto se passa com a nossa representação do cubo, não se passará com a representação de outros sólidos?

Embora fora do âmbito do nosso curso, chamamos a atenção para o interesse de ver se são transferíveis as propriedades dos sólidos (em particular dos platónicos) para os grafos (ou reciprocamente, claro!).


Tarefas 2.1.1

2.1.1) Procure na internet referências a Hamilton e a Kuratowski. Esboce um resumo biográfico de um deles, com indicações das fontes (sites).

2.1.1.1. Desenhe os sólidos platónicos em projecção cavaleira, com indicação dos vértices e das arestas. Utilizando o resultado de Kuratowski, verifique se os grafos respectivos são planares.

a) Á semelhança do que foi feito com o cubo, tente desenhar grafos equivalentes com arestas que só se intersectem nos vértices.

b) Determine, se existirem, circuitos de Hamilton sobre esses grafos.


voltar ao sumário