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

Terceira Lista de Exercícios (30 pontos) - Entrega: 26 de outubro

1.

(10 pontos)
Prove que o problema do fluxo máximo é ilimitado se e só se existe um caminho dirigido de $s$ a $t$ em que todos os arcos têm $u$_e=+∞ .

2.

(5+5 pontos)
Mostre que se $S$₁ e $S$₂ são cortes de capacidade mínima, então $S$₁ ∩ S₂ e $S$₁ ∪S₂ são cortes de capacidade mínima.

3.

(10 pontos)
Dado um grafo dirigido $G$, com capacidade de fluxo $u$ nos arcos, encontre um corte $R$ tal que

$\sum$_{e ∈δ⁺(R)} u_e - ∑_{e ∈δ^-(R)} u_e

é mínimo possível.

4.

(10 pontos)
Ache um fluxo máximo e um corte mínimo para o grafo abaixo. $$\epsffile{l3f1.eps}$$