Matemática 11.º Ano: Circuito de Euler (Exame 2011)

Na Figura 1, encontra-se o grafo que serve de modelo aos percursos utilizados pela RecSol, uma empresa de recolha de resíduos sólidos.
Cada vértice do grafo representa um local de recolha de resíduos sólidos, e cada aresta representa uma estrada que liga dois desses locais.
Na Tabela 2, encontram-se registadas as distâncias mínimas, em metros, entre cada dois locais de recolha de resíduos sólidos, representados pelos vértices do grafo da Figura 1, quando se percorrem as estradas representadas pelas arestas do mesmo grafo.

	A	B	C	D	E	F	G
A	—	1253	—	—	—	—	1248
B	—	—	1421	—	712	938	—
C	—	—	—	911	941	—	—
D	—	—	—	—	1001	—	—
E	—	—	—	—	—	1198	—
F	—	—	—	—	—	—	832
G	—	—	—	—	—	—	—

Ο António, um motorista da empresa RecSol, quer verificar se existem resíduos abandonados ao longo das estradas.
Pretende partir do local representado pela letra A, percorrer todas as estradas, sem as repetir, e regressar ao mesmo local.
Podem todas as pretensões do António ser satisfeitas, em simultâneo?
Justifique a sua resposta.

Este item pode ser resolvido por, pelo menos, dois processos. 1.º Processo Apresenta-se, a seguir, um exemplo de resposta (ver nota). O que o António pretende implica a existência de circuitos de Euler no grafo que serve de modelo aos percursos utilizados pela RecSol. Mas não é possível satisfazer as pretensões do António, em simultâneo, porque o grafo tem dois vértices de grau ímpar, o vértice C e o vértice F, o que significa que não respeita a condição necessária e suficiente para que um grafo conexo admita circuitos de Euler. Tal como o exemplo ilustra, para que a resposta a este item seja considerada correcta e completa, o examinando deve: A) referir que a satisfação das pretensões do António implica que o grafo respeite a condição necessária e suficiente para que um grafo conexo admita circuitos de Euler; B) referir que o grafo não respeita a condição necessária e suficiente para que um grafo conexo admita circuitos de Euler, por ter vértices de grau ímpar (ou equivalente); C) concluir que não é possível satisfazer as pretensões do António, em simultâneo. 2.º Processo Apresenta-se, a seguir, um exemplo de resposta (ver nota). Admitindo que é possível satisfazer, em simultâneo, todas as pretensões do António, como este parte do local representado pela letra A, num dado momento chega ao local representado pela letra C, por exemplo. Nessa chegada a C, o António percorreu uma das três arestas que incidem nesse vértice. Ao sair de C, percorre uma das duas arestas restantes, ficando uma por percorrer. Quando a última for percorrida, terá de ser no sentido de chegada a C e não de saída. Logo, o António não regressa a A, porque não pode sair de C, visto que as três arestas que incidem em C foram já percorridas. Assim, somos conduzidos a uma contradição. Por conseguinte, as pretensões do António não podem ser realizadas conjuntamente. Tal como o exemplo ilustra, para que a resposta a este item seja considerada correcta e completa, o examinando deve: A) indicar um vértice ímpar; B) referir que um vértice ímpar admite duas entradas, mas apenas uma saída; C) concluir que não é possível satisfazer as pretensões do António, em simultâneo. A classificação faz-se de acordo com os níveis de desempenho a seguir descritos.

Descritores do nível de desempenho no domínio específico da disciplina	Descritores do nível de desempenho no domínio da comunicação escrita em língua portuguesa			Níveis*
	1	2	3
3	A resposta contempla, correctamente, os três pontos.	18	19	20
Níveis	2	A resposta contempla, correctamente, apenas os pontos A e B, ou apenas os pontos B e C.	12	13	14
	1	A resposta contempla, correctamente, apenas o ponto A ou apenas o ponto B.	6	7	8

* Descritores apresentados nos Critérios Gerais de Classificação. Nota - Se o examinando apresentar uma resposta equivalente, considerada cientificamente válida, os elementos de resposta cientificamente válidos devem ser pontuados segundo procedimentos análogos aos previstos nos descritores apresentados.