Matemática Aplicada: Grafos e Caminho de Euler (Exame 2008 - 11.º Ano)

Uma Câmara Municipal elaborou um contrato com a empresa FUTUROLIMPO, empresa especializada na recolha selectiva de resíduos.
Na figura, apresenta-se um «mapa» de uma zona residencial desse município, que possui oito espaços de recolha selectiva de resíduos (ecopontos).
Os oito ecopontos estão representados por E1, E2, E3, E4, E5, E6, E7 e E8.
Designa-se por «troço de rua» a ligação entre dois ecopontos adjacentes, isto é, o percurso que se efectua para ir de um desses ecopontos ao outro sem passar por mais nenhum.
Os moradores da mesma zona residencial reclamaram das condições de alguns troços de rua de acesso aos ecopontos.
A Câmara Municipal decidiu enviar um funcionário especializado, para inspeccionar as condições dos mesmos.
Admita que o funcionário decidiu iniciar e terminar as suas inspecções junto do mesmo ecoponto.
No entanto, ao analisar o «mapa» da zona em causa, concluiu que, para concretizar essa decisão, não tinha possibilidade de inspeccionar todos os troços de rua, passando por cada um deles uma única vez.
Por isso, de forma a rendibilizar o tempo da inspecção, procurou encontrar um percurso cujo número de troços de rua a percorrer fosse o menor possível, garantindo o início e o fim da inspecção junto do mesmo ecoponto.
Num pequeno texto:

• indique, justificando, a razão que levou o funcionário a concluir da impossibilidade de inspeccionar todos os troços de rua, passando por cada um deles uma única vez, tendo em conta que ele pretende iniciar e terminar a inspecção junto do mesmo ecoponto;

• indique, ainda, um percurso que se inicie e termine no ecoponto E₂ e que permita ao funcionário inspeccionar todos os troços de rua, sendo o número de troços de rua a percorrer o menor possível.
Apresente o percurso na forma de uma sequência, utilizando as designações dos ecopontos.
Comece, obrigatoriamente, por modelar, através de um grafo, o «mapa» da zona residencial apresentado, considerando que os vértices representam os ecopontos e que as arestas representam os troços de rua.

Apresenta-se, a seguir, um exemplo de resposta: Um grafo que representa a situação descrita é, por exemplo: [Grafo que representa Ecopontos E1 a E8 e as ruas de ligação] Iniciando e terminando a inspecção junto do mesmo ecoponto, o funcionário concluiu que não conseguia inspeccionar todos os troços de rua, passando por cada um deles uma única vez, pois trata-se de averiguar se um grafo que modele a situação descrita admite um circuito de Euler. Ora, sabe-se que a condição necessária e suficiente para que um grafo conexo admita tal circuito é a de que todos os seus vértices tenham grau par. Como existem vértices de grau ímpar (vértices E2 e E8), o funcionário teria de repetir, pelo menos, um troço de rua. Assim, averiguando qual o percurso a escolher para que o número de troços de rua a percorrer fosse o menor possível, bastava repetir apenas dois troços de rua, por exemplo, o caminho que une os ecopontos (vértices) E2 e E5 e o caminho que une os ecopontos E5 e E8. [Grafo eulerizado com duplicação de arestas E2-E5 e E5-E8] De facto, procedendo à eulerização do grafo, obtém-se um grafo que modela a nova situação descrita e que, além de ser conexo, tem todos os seus vértices de grau par, pelo que é possível percorrer todos os troços de rua (arestas) deste novo grafo, sem repetir nenhum troço de rua, começando e terminando o percurso num mesmo vértice. Por exemplo, conforme solicitado, um percurso possível, começando e terminando no ecoponto (vértice) E2, será: E2E4E5E6E1 E7 E3E7E8E3E2E5E8E5E2. Tal como é exigido no enunciado e o exemplo acima ilustra, para que a resposta possa ser considerada correcta e completa, deverá estar de acordo com os seguintes pontos: • apresenta um grafo que modela a situação descrita; • apresenta a justificação solicitada. Apresenta um grafo que modela a situação. (10 pontos) Justificação solicitada. (25 pontos) A classificação a atribuir à justificação deve estar de acordo com os seguintes níveis de desempenho (ver notas 1, 2 e 3).

	Descritores do nível de desempenho no domínio da comunicação escrita em língua portuguesa
Descritores do nível de desempenho no domínio específico da disciplina	1	2	3
Níveis	6 Justifica, correctamente, a conclusão do funcionário. Indica, correctamente, quais as duas arestas a duplicar. Indica, correctamente, um circuito euleriano que inicia e termina no vértice E2.	22	24	25
	5 Justifica, correctamente, a conclusão do funcionário. Indica, correctamente, quais as duas arestas a duplicar. Indica um circuito euleriano que inicia e termina no vértice E2, apresentando somente uma incorrecção.	18	20	21
	4 Justifica, correctamente, a conclusão do funcionário. Indica, correctamente, quais as duas arestas a duplicar. ou Não justifica a conclusão do funcionário ou a justificação apresentada está incorrecta. Indica, correctamente, um circuito euleriano que inicia e termina no vértice E2.	14	16	17
	3 Justifica, correctamente, a conclusão do funcionário. Indica, correctamente, apenas uma das duas arestas a duplicar. ou Não justifica a conclusão do funcionário ou a justificação apresentada está incorrecta. Indica um circuito euleriano que inicia e termina no vértice E2, apresentando somente uma incorrecção.	10	12	13
	2 Somente justifica, correctamente, a conclusão do funcionário. ou Não justifica a conclusão do funcionário ou a justificação apresentada está incorrecta. Indica, correctamente, quais as duas arestas a duplicar.	6	8	9
	1 Não justifica a conclusão do funcionário ou a justificação apresentada está incorrecta. Indica, correctamente, apenas uma das duas arestas a duplicar.	2	4	5

* Descritores apresentados no primeiro quadro constante nos Critérios gerais de classificação da prova. Notas: 1. Apenas podem ser atribuídas classificações correspondentes a um dos valores constantes do quadro. Não há lugar a classificações intermédias. 2. No caso de a resposta não atingir o nível 1 de desempenho no domínio específico da disciplina, a classificação a atribuir é de zero pontos. Nesse caso, não é classificado o desempenho no domínio da comunicação escrita em língua portuguesa. 3. No caso de, ponderados todos os dados contidos nos critérios, permanecerem dúvidas quanto ao nível a atribuir, deve optar-se pelo mais elevado dos dois em causa.