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 $s$ a todos os outros vértices em um grafo dirigido $G$ 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 $u,v$ do grafo por dois arcos, um deles indo de $u$ para $v$ e o outro de $v$ para $u$. 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 $w\; \in V$ 
Inicialize 

$W\; :=\; \{w\}$ e 

$T\; :=\; \varnothing$. 
Enquanto $W\; \ne V$ 
		 Selecione uma aresta $uv\; \in E$ com $u\; \in W$ e 

$v\; \in V\; \setminus W$ 
		 tal que 

$c(uv)\; =min\{c(ij)\; |\; i\; \in W,\; j\; \in V\; \setminus W\}$ 
		 Atualize 

$T\; :=\; T\; \cup \{uv\}$ e 

$W\; :=\; W\; \cup \{v\}$. 

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.