BCM0506_lista3

Prévia do material em texto

BC0506 – Comunicação e Redes – Atividade Prática 1 
Prof. José Artur Quilici Gonzalez – CMCC – UFABC – 2012 
 
1. (0,5) Considere o seguinte mapa do Estado de São Paulo: 
Figura 1 – Mapa com algumas cidades importantes do estado de São Paulo 
 
1.1. Faça uma representação na forma de grafo das cidades e de suas conexões, como 
assinaladas no mapa da Figura 1. 
1.2. Utilizando o Algoritmo de Dijkstra, encontre o caminho mínimo para todas as cidades 
assinaladas, tendo como ponto de origem a cidade de Campinas. 
Apresente uma tabela explicativa e/ou ilustrações de cada passo do Algoritmo de Dijkstra. 
Se forem usados programas computacionais ou planilhas, anexe estes recursos para que os 
resultados obtidos possam ser reproduzidos. 
 
Algoritmo de Prim 
 Uma árvore é um grafo conectado sem ciclo, e constitui uma alternativa interessante 
quando se deseja conectar todos os nós de um grafo com uma extensão mínima de arestas. 
Dado um grafo conectado, o Algoritmo de Prim ajuda a encontrar quais arestas redundantes 
podem ser retiradas para que todos os nós ainda continuem conectados através de uma 
árvore com custo mínimo. Note que uma solução desse tipo geralmente produz um resultado 
diferente daquele produzido pelo Algoritmo de Dijkstra. 
Considere, por exemplo, como origem a cidade de Campinas no mapa de SP fornecido. 
O Algoritmo de Dijkstra possivelmente encontraria como o caminho mínimo entre Campinas, 
São Paulo e São José dos Campos os trechos de 90 Km (Campinas-São Paulo) e 130 Km 
(Campinas-São José dos Campos), enquanto que o Algoritmo de Prim possivelmente indicaria 
os trechos Campinas-São Paulo (90 Km) e São Paulo-São José dos Campos (90 Km), porque o 
caminho 90+90=180 Km é menor que 90+130=210 Km de estradas, e as três cidades 
continuam igualmente conectadas. 
A seguir, vamos apresentar uma versão simplificada do Algoritmo de Prim usando 
como exemplo o grafo da Figura 2. 
 
 
 
 
 
Figura 2 – Exemplo de grafo conectado para aplicação do Algoritmo de Prim 
Dado um nó de origem, digamos o nó v1 do grafo da Figura 2, o Algoritmo de Prim escolhe a 
menor aresta associada a este nó (aresta com valor 2) e, a seguir, inclui o nó v2 dentre os nós já 
descobertos. Agora o algoritmo considera qual das arestas partindo de v1 ou v2 tem o menor 
valor (neste caso, a aresta de valor 1, partindo de v2), e assim sucessivamente. O grafo da 
Figura 3 e a Tabela 1 mostram o resultado da aplicação do Algoritmo de Prim no grafo da 
Figura 2. 
 
 
 
 
 
 
Figura 3 – Árvore mínima após a aplicação do Algoritmo de Prim 
 
 
v1 
v2 
v3 
v4 
v5 
2 
4 
3 
2 
1 2 
5 
1 
2 
v1 
v2 
v3 
v4 
v5 
2 
2 
1 
1 
Iteração u 1 2 3 4 5 
0 v1 2, (v1, v2) 4, (v1, v3) 3, (v1, v4) +∞,? 
1 v2 1, (v2, v3) 2, (v2, v4) 5, (v2, v5) 
2 v3 1, (v3, v4) 2, (v3, v5) 
3 v4 2, (v3, v5) 
4 v5 
 
2. (0,5) Suponha que lhe tenha sido atribuída a seguinte tarefa relacionada ao mapa da Figura 
1. Suponha que as 10 cidades mostradas no mapa da Figura 1 já possuem uma rede de 
interligação que acompanha o traçado das estradas assinaladas. Uma nova rede de fibras 
óticas deve interligar as 10 cidades de SP mostradas no mapa, mas como o custo da instalação 
de fibras óticas é muito elevado, as autoridades desejam encontrar a Árvore de Prim do grafo 
que indicariam quais arestas precisam ser substituídas com fibra ótica. O restante das arestas, 
com conexões antigas, permanecerá como redundância para situações de emergência, para o 
caso em que alguma das conexões de fibras óticas tenha se rompido. 
2.1 Pesquise um pouco mais sobre o Algoritmo de Prim, e apresente o grafo com as conexões 
de fibras óticas, assim como as tradicionais, para que os engenheiros possam calcular o custo 
da obra. 
2.2 Apresente uma tabela explicativa e/ou ilustrações de cada passo do Algoritmo de Prim. Se 
forem usados programas computacionais ou planilhas, anexe estes recursos para que os 
resultados obtidos possam ser reproduzidos. 
 
Instruções Gerais 
Esta Atividade Prática poderá ser feita individualmente ou em equipe, com até quatro 
componentes, e terá a validade de 10% da nota final da disciplina. 
O prazo de entrega no Tidia (arquivos eletrônicos do tipo .doc, .odt e .pdf) será até a próxima 
quinta-feira 11.10.12, com tolerância até o domingo 14.10.12, porém com uma penalização de 
50% da nota da Atividade Prática. 
Não se esqueça de colocar todas as fontes consultadas, como livros e páginas da web (com a 
respectiva data de acesso). 
 
 
 
Referências Bibliográficas 
- A. V. Aho, J. E. Hopcroft, J. D. Ullman. “Data Structures and Algorithms”, Addison-Wesley, 
1987. 
 
- Gerez, S. H. Algorithms for VLSI Design Automation. West Sussex, Inglaterra: John Wiley & 
Sons Ltd., 1999. 
- http://maps.google.com/ Google Maps. Acessado em 19.09.12.