Matemática 11.º Ano: Árvore Geradora Mínima (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	—	—	—	—	—	—	—

A RecSol vai ligar todos os locais de recolha de resíduos sólidos com um cabo de fibra óptica, utilizando algumas das estradas representadas no grafo da Figura 1.
De modo a usar a menor extensão de cabo de fibra óptica, a empresa contactou dois especialistas em instalação de fibra óptica, o João e o José.
O João afirma, sem recurso a nenhum método, que a ligação que requer menos cabo é {(A,B),(F,G),(B,F),(B,E),(C,E),(C,D)}
O José propõe uma ligação apoiando-se no uso do algoritmo seguinte.
Algoritmo
Passo 1:
Escolhem-se as duas arestas com o menor valor de distância.
Passo 2:
Escolhe-se a aresta seguinte com o menor valor de distância, desde que essa aresta não feche um circuito.
Passo 3:
Repete-se o ponto anterior até que todos os vértices façam parte da árvore, tendo em conta as regras seguintes:

• se houver empate na escolha de arestas, selecciona-se a aresta aleatoriamente;

• se a aresta a escolher fechar um circuito, essa aresta não deve ser considerada.
Indique qual das duas propostas deve escolher a empresa, de modo a usar a menor extensão de cabo de fibra óptica.
Na sua resposta, deve:

• determinar o número de metros da proposta do João;

• aplicar ao grafo da Figura 1 o algoritmo proposto pelo José;

• determinar o número de metros da proposta do José;

• apresentar uma conclusão sobre a escolha da empresa.

Calcular o número de metros de cabo de fibra óptica da proposta do João (5587 metros) 1 ponto Definir o percurso da proposta do José usando o conjunto de ligações {(B,E),(F,G),(C,D),(B,F),(C,E),(A,G)} (1 + 1 + 1 + 1 + 1 + 1) 6 pontos Calcular o número de metros da proposta do José (5582 metros) 1 ponto Apresentar a conclusão relativa à escolha da empresa 2 pontos