Novas tarefas:
 
Primeira.
Lembra-se desta figura na sua infância?
Consegue percorrer todas as suas arestas sem levantar o lápis? Será que isso correpsonde a admiitr um circuito de Euler? Justifique as suas respostas.
 
Segunda
Desenhe o grafo para para a vigilância e controle dos parcómetros assinalados do território acima. Atribua a cada vertex a sua valência e verifique se o grafo é conexo.
Para esta rede de ruas, desenhe o grafo que pode ser útil para um giro de recolha de lixo. Suponha que todas as ruas têm dois sentidos e que passar uma só vez por cada rua chega para fazer a recolha dos dois lados da rua.
 
Terceira.
No grafo acima, temos um espaço onde podem estacionar automóveis controlados por parcómetros, para o qual a patrulha não pode ser feita seguindo um circuito de Euler. Que passeio pode ser abandonado para que se possa fazer um giro por circuito de Euler?
 
Quarta.
Encontre um circuito em cada um dos grafos ao lado que considere todas as arestas e tenha o menor número possível de repetições.
Quinta.
Um grafo G representa uma rede de ruas para serem percorridas por um carteiro que tem de atravessar cada rua duas vezes, uma por cada lado da rua. Nesse grafo G, as arestas representam os passeios. Será que qualquer grafo deste tipo admite um circuito de Euler? Explique a sua resposta.
 
Suponha que para um certo grafo é possível torná-lo desconexo, retirando-lhe uma aresta. Mostre que um grafo deste tipo tem pelo menos um vértice de valência ímpar. (Mostre que tal grafo não admite um circuito de Euler)
 
A palavra "valência" é também usada em Química. Tente lembrar-se do significado químico da palavra e explique em quê o uso da palavra se assemelha em Química e no estudo dos grafos.
 
Será possível que uma rede de ruas dê origem a um grafo desconexo? Se tal for possível, desenhe uma rede, para exemplo, de blocos e ruas com parcómetros . E desenhe o respectivo grafo desconexo.
 
Que razões práticas nos podem levar a considerar a necessidade de voltarmos aos pontos de partida nas nossas voltas? Responda separadamente para os seguintes casos, (e se houver algum caso em que considere não ser nada necessário voltar ao ponto de partida explique porquê):
(a) Patrulha dos parcómetros; (b) Limpeza das ruas; (c) Distribuição postal.
 
 
Sexta.
Escreva uma carta a um chefe de serviços que trate do controle e vigilância dos parcómetros sugerindo como as técnicas da teoria de grafos devem ser usadas. Lembre-se que a pessoa que vai receber a carta pode não ter formação matemática para além daquela que lhe permite a boa vontade de ler uma coisa enquanto lhe parecer suficientemente clara.


voltar ao sumário