Admita que, no distrito de Castelo Branco, se pretende adotar uma nova tecnologia na iluminação de estradas.
Na Tabela 3, apresenta-se a extensão, em quilómetros, das estradas onde se poderá adotar esta tecnologia.
Tabela 3
| Benquerença (B) | Louriçal do Campo (L) | Oleiros (O) | Torrozelo (T) | |
|---|---|---|---|---|
| Alcafozes (A) | 60 | 51 | 124 | 167 |
| Benquerença (B) | ---- | 39 | 68 | 173 |
| Louriçal do Campo (L) | ---- | ---- | 100 | 144 |
| Oleiros (O) | ---- | ---- | ---- | 112 |
Não sendo viável, por razões económicas, adotar esta tecnologia em todas as estradas, decidiu-se, numa fase inicial, proceder à sua adoção somente em algumas delas.
Para a seleção das estradas recorreu-se ao algoritmo seguinte.
- Constrói-se um grafo, cujos vértices representam as localidades, selecionando-se, sucessivamente, as menores extensões de estradas entre elas, tendo-se em conta que:
- se a aresta a que corresponde a extensão selecionada levar à formação de um circuito, essa aresta não deve ser considerada;
- caso contrário, essa aresta deve ser considerada.
- O algoritmo termina quando, no grafo, o número de arestas é igual ao número de vértices menos um.
Determine, nestas condições, o número de quilómetros de estrada que o projeto de iluminação deve contemplar na sua fase inicial.
Na sua resposta, apresente o grafo que resulta da aplicação do algoritmo, indicando o peso de cada aresta.
Comentários
Neste momento, não há comentários para este exercício.
Para comentar, por favor inicia sessão ou cria uma conta.