Next: About this document ...
MAC-IME-USP CARLOS EDUARDO FERREIRA
SALA 297A TEL.: 818 6140
E-MAIL cef@ime.usp.br
a. Desenhe a árvore .
b. Mostre as alterações nos vetores correspondentes a retirar a aresta (5,9) e colocar a aresta (1,2).
a. .
b.
c. Para todo tal que , .
d. Se , então é uma solução ótima.
Seja
e considere o circuito formado por em .
Considere ainda
como o conjunto das arestas de que têm
orientação contrária à de em . Defina,
e mostre que:
e. .
f. .
g. Se e então o problema é ilimitado.
Carlos Eduardo Ferreira