Os membros da Associação Ambientalista de Avelares (AAA) têm o cuidado de realizar conferências que incentivem à separação de resíduos.
Na última conferência, compareceram vários associados da AAA, dos quais três quartos eram mulheres.
Questão:
No parque municipal de Avelares, vão ser instalados oito bebedouros em locais previamente selecionados, designados por A, B, C, D, E, F, G e H, que serão interligados através de uma canalização.
Na Tabela 2, apresenta-se o comprimento, em metros, das ligações que é possível estabelecer entre os diversos locais.
Tabela 2
| B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|
| A | 500 | 620 | --- | 840 | --- | --- | 502 |
| B | 505 | --- | 446 | --- | 800 | --- | |
| C | 1140 | 850 | --- | 754 | --- | ||
| D | --- | 976 | 721 | 952 | |||
| E | 700 | --- | --- | ||||
| F | 412 | 1310 | |||||
| G | 1360 |
De modo a minimizar o custo da canalização, construiu-se um grafo, aplicando o método que a seguir se descreve.
- Seleciona-se a ligação de menor comprimento (se houver mais do que uma, escolhe-se ao acaso uma delas).
- Em seguida, seleciona-se, de entre as ligações restantes, a de menor comprimento, desde que esta não leve à formação de um ciclo.
- Termina-se quando todos os locais onde serão instalados bebedouros estiverem ligados.
Determine o comprimento total da canalização.
Na sua resposta, apresente o grafo que resulta da aplicação do método descrito.
Comentários
Neste momento, não há comentários para este exercício.
Para comentar, por favor inicia sessão ou cria uma conta.