CLRS - Lema Maxflow de fluxo aumentado 26.1 - não entende o uso de def. em prova

8

Em Cormen et. al., Introdução aos algoritmos (3ª ed.), não entendo uma linha na prova do Lema 26.1 que afirma que o fluxo aumentadoff é um fluxo em G e é st |ff|=|f|+|f| (isto é pp. 717-718).

Minha confusão: ao discutir a conservação do fluxo, eles usam a definição deff na primeira linha para dizer que para cada uV{s,t}

vV(ff)(você,v)=vV(f(você,v)+f(você,v)-f(v,você)),

onde o caminho aumentado é definido como

(ff)(u,v)={f(u,v)+f(u,v)f(v,u)if (u,v)E,0otherwise.

Por que eles podem ignorar a cláusula 'caso contrário' no somatório? Não acho que a primeira cláusula seja zerada em todos esses casos. Eles usam a conservação do fluxo def e f de algum modo?

Dominik Peters
fonte

Respostas:

9

Nota: As notações e definições usadas abaixo são emprestadas da terceira edição do livro.

Para responder a essa pergunta, primeiro observe que se (u,v)E, então, por definição de fluxo,

f(u,v)=f(u,v)=(ff)(u,v)=0.

Além disso, desde f(v,u)cf(u,v)=f(u,v), obtém-se que f(v,u)=0. Isso simplesmente implica que(u,v)E,

(ff)(você,v)=f(você,v)+f(você,v)-f(v,você)=0 0.

Portanto, a definição de fluxo aumentado pode ser generalizada para todos (você,v)V×V para ser o seguinte:

(ff)(você,v)=f(você,v)+f(você,v)-f(v,você).

O restante da prova segue dessa observação que, é claro, não é explicitamente explicada no texto.

PS Observe que a definição formal de fluxo na terceira edição do livro é significativamente diferente daquela da segunda edição. Em particular, na segunda edição, há uma propriedade de fluxo denominada simetria de inclinação que requerf(você,v)=-f(v,você),você,vV. Essa propriedade foi removida na terceira edição devido às suposições de que(v,você)E E se (u,v)E e f(v,u)=0 E se (v,u)E. Por esse motivo, as definições de conservação de fluxo em duas edições também são diferentes. De fato, muitas dessas confusões advêm dessa mudança de definição que, presumivelmente, pretende simplificar as provas, mas acabou sendo mais desconcertante. Pessoalmente, preferiria me ater à segunda edição do livro para este capítulo em particular.

Todos
fonte