Sobre o famoso problema de Königsberg
 
 
Retomemos a situação

O rio Pregel tem duas ilhas. Estas estão unidas por uma ponte. Uma ilha tem uma ponte que a une a ambas as margens; a outra tem duas pontes para cada margem. Podem os cidadãos de Conisberga atravessar todas as 7 pontes num só passeio contínuo?
 
Que grafo escolher? Isto é: que pontos e que arestas?
Parece-nos que o mais sensato será pensar na seguinte figura:

 
 
e o grafo que representa a situação é
Sem querer complicar coisa alguma, um cidadão pode partir de A e fazer o passeio contínuo ACDACBDB, em que percorre todos as arestas visitando todos os pontos e percorrendo todas as arestas.
Mas não era concerteza este passeio contínuo que constituia problema. O problema dificil e que interessava resolver a um cidadão qualquer seria encontrar o circuito mais económico possível (ou o passeio completo e menos cansativo): partir de casa (A, por exemplo) e voltar a casa (A) passando por todas as pontes, sem repetir qualquer das pontes (ou arestas).
 
Este tipo de circuito óptimo (que tomou o nome de Euler) é que é impossível para os cidadãos de Königsberg.
 
Para que não se repetissem arestas, seria preciso que o número de saídas de A fosse igual ao número de entradas em A. Se sairmos por uma das pontes de A para C, podemos voltar mais tarde por CA ou por DA. Se voltarmos por DA e quisermos passar pela segunda ponte de A para C, não podemos voltar sem repetir uma das pontes. Se voltarmos por CA, falta-nos fazer a ponte AD e para voltar....
 
Será que podemos mesmo descrever todos os circuitos possíveis (a começar e acabar em A)?
 
 
Oitava tarefa
Verifique se ADBCBCACDA repesenta um circuito completo e indique quais são as arestas (pontes) repisadas.
Será uma tarefa humanamente recomendável essa de descrever todos os circuitos possíveis (a começar e a acabar em A)?