Next: About this document ...
MAC-IME-USP CARLOS EDUARDO FERREIRA
SALA 297A TEL.: 818 6140
E-MAIL cef@ime.usp.br
MAC 325 - Otimização Combinatória - MAC 5781
Prim. Lista de Exercícios (30 pontos) - Entrega: 14 de setembro
- 1.
- (5 pontos)
Considere o problema de achar um caminho mínimo de um vértice a todos os
outros vértices em um grafo dirigido com custos negativos e positivos
nos arcos. A idéia de somar a todos os arcos o módulo do custo do arco de
menor custo (caso este seja negativo) e então aplicar o algoritmo de Dijkstra
funciona? Mostre ou dê um contra-exemplo.
- 2.
- (10 pontos)
Mostre que se um grafo contém um circuito de custo negativo, o algoritmo de
Bellman-Ford o acha no último loop.
- 3.
- (5 pontos)
Considere agora o problema de encontrar caminhos mínimos em grafos não
dirigidos. Uma idéia seria trocar cada aresta do grafo por dois arcos,
um deles indo de para e o outro de para . Mostre que a idéia
funciona, ou dê um contra-exemplo.
- 4.
- (10 pontos)
O Algoritmo de Prim para calcular uma árvore geradora de peso mínimo
de um grafo pode ser descrito da seguinte maneira:
Escolha um v'ertice arbitr'ario
Inicialize
e
.
Enquanto
Selecione uma aresta com e
tal que
Atualize
e
.
a. Mostre que o algoritmo acima está correto.
b. Qual é a complexidade da melhor implementação possível do algoritmo
acima?
- 5.
- (20 pontos)
Implemente um dos algoritmos para caminhos mínimos em grafos dirigidos vistos
em sala de aula (Dijkstra ou Bellman-Ford). Teste para vários exemplos e faça
um pequeno relatório de sua implementação.
Next: About this document ...
Carlos Eduardo Ferreira
8/27/1998