Parte I. (5 horas)

Um grafo para um problema (Um exemplo de problema e de grafo). Concretização de situações e problemas que podem resolver-se utilizando grafos como modelo.

 

Um problema famoso para começar

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?

Euler deu resposta a esta questão e a todas as questões do mesmo tipo.

 


Primeira tarefa:

Segunda tarefa: