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: 9 de novembro

1.

(10 pontos)
Ache um fluxo máximo e um corte mínimo no grafo abaixo usando o algoritmo ``push-relabel'' visto em sala de aula. $$\epsffile{l3f1.eps}$$

2.

(5 pontos)
Enuncie e prove com detalhe a versão do Teorema de Menger para grafos orientados e caminhos disjuntos nos arcos.

3.

(10 pontos)
Mostre que se $x$ é um pré-fluxo viável para o qual existe uma rotulação válida correspondente, então

$d(v)\; :=min\{\; dist$_x(v,t), n+dist_x(v,s)}

é uma rotulação válida.

4.

(10 pontos)
Ache para o grafo abaixo um emparelhamento máximo e um cobertura mínima. $$\epsffile{l4f1.eps}$$

5.

(10+5 pontos)
a. Mostre que um grafo bipartido em que todo vértice tem grau $k\; \ge 1$ tem um emparelhamento perfeito.
b. Mostre que tal grafo tem $k$ emparelhamentos perfeitos disjuntos.