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