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
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.
- 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 é um pré-fluxo viável para o qual existe uma rotulação válida
correspondente, então
é uma rotulação válida.
- 4.
- (10 pontos)
Ache para o grafo abaixo um emparelhamento máximo e um cobertura mínima.
- 5.
- (10+5 pontos)
a. Mostre que um grafo bipartido em que todo vértice tem grau tem
um emparelhamento perfeito.
b. Mostre que tal grafo tem emparelhamentos perfeitos disjuntos.
Carlos Eduardo Ferreira
1998-12-22