lista4 CR

Prévia do material em texto

BCM0506 - Comunicação e Redes
Lista 04
Prof. Valério Ramos (baseada na lista do Prof. Jesus Mena-Chalco)
PARTE 1
Questão 1 (1 ponto):
Um químico deseja embarcar os produtos A, B, C, D, E, F, X usando o menor número de caixas. Alguns produtos não
podem ser colocados em uma mesma caixa porque reagem. Os produtos A, B, C, X reagem dois-a-dois; A reage com F
e com D e vice-versa; E também reage com F e com D e vice-versa. Desenhe um grafo que modele essa situação e use-
o para descobrir o menor número de caixas necessárias para embarcar os produtos
com segurança.
PARTE 2
Escolha um dos grafos G, conexos e não-direcionados, disponíveis em Arquivos_Lista04.zip.
Questão 2 (3 pontos):
Execute o algoritmo de Busca em Profundidade a partir do vértice 1 do grafo G.
2.1) Indique a sequência de vértices visitados, considerando na busca a preferência para vértices de menor índice.
2.2) Indique a sequência de vértices visitados, considerando na busca a preferência para vértices de maior índice.
Nota: O algoritmo de Busca em profundidade, visto em aula, opera sobre grafos não-ponderados. Assim, para este
exercício, assuma que o grafo não tem pesos/custos nas arestas.
Questão 3 (3 pontos):
Simule o algoritmo de Dijkstra, considerando como origem o vértice 1, para calcular os caminhos mínimos (custos) para
todos os outros vértices do grafo G.
3.1) Indique a distância da origem até o vértice 15.
3.2) Indique o vértice com menor distância (i.e. o vértice com menor custo, exceto o vértice 1). Em caso de existir
empate, na menor distância, indique o vértice de maior índice.
3.3) Indique o vértice com maior distância (i.e. o vértice com maior custo). Em caso de existir empate, na maior distância,
indique o vértice de maior índice.
Questão 4 (3 pontos)
Uma árvore é um grafo conectado sem ciclo, e constitui uma alternativa interessante quando se deseja conectar todos os
vértices 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 vértices 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.
A seguir, é apresentada uma versão simplificada do Algoritmo de Prim usando como exemplo o grafo da Figura 1a.
(a) (b)
Fig. 1 – Exemplo de grafo conectado para aplicação do Algoritmo de Prim.
Dado um vértice de origem, digamos o vértice v1 do grafo da Figura 1a, o Algoritmo de Prim escolhe a menor aresta
associada a este vértice (aresta com valor 2) e, a seguir, inclui o vértice v2 dentre os vértices 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 1b mostra o resultado da aplicação do Algoritmo de Prim no grafo da
Figura 1a.
Para nosso exemplo, a árvore obtida terá um custo total de 6 (somatória de todos os pesos das arestas da árvore).
Pesquise um pouco mais sobre o Algoritmo de Prim.
4.1) Para o grafo G simule o Algoritmo de Prim a fim de determinar uma árvore de custo mínimo.