MO417 - Questão para a prova oral

Número: 109

Enunciado: Königsberg era uma cidade da Prussia, situada `as margens do rio Pregel, que cortava a cidade de maneira bastante peculiar, criando duas ilhas. Sete pontes ligavam as duas ilhas entre si e ao continente. Durante muito tempo várias pessoas se perguntaram se seria possível fazer um passeio pela cidade passando por cada ponte exatamente uma vez. A figura abaixo representa de forma esquemática a cidade de Königsberg e o grafo a ela relacionado. Este problema reduz-se a:

1. encontrar uma árvore espalhada mínima num grafo
2. encontrar um caminho de peso mínimo num grafo
3. encontrar um ciclo hamiltoniano num grafo
4. encontrar um passeio euleriano num grafo
5. NDA

Autor: Juliana Galvani Greghi