Baklengs flyt i 1. og 2. utgave

I tidligere utgaver av læreboka tillot de antiparallelle kanter (dvs., både $(u,v)\in E$ og $(v,u)\in E$), men i de nyeste utgavene tillater de ikke dette (for å gjøre enkelte ting enklere). Det har også noe å si for definisjonen av flyt!

I 2. utgave skal flytfunksjonen $f$ tilfredsstille følgende tre krav (sitat fra 2. utg., s. 580):

Capacity constraint	For all $u, v\in V$ , we require $f(u,v)\leq c(u,v)$ .
Skew symmetry	For all $u, v\in V$ , we require $f(u,v) = -f(v,u)$ .
Flow conservation	For all $u\in V - \{s,t\}$ , we require $\sum_{v\in V}f(u,v) = 0$ .

Siden de forbyr antiparallelle kanter (og krever at man skriver dem om ved å splitte opp én av dem), så kan de forenkle kravene til flytfunksjonen til følgende (sitat fra 3. utg., s. 709):

Capacity constraint	For all $u, v\in V$ , we require $0\leq f(u,v)\leq c(u,v)$ .
Flow conservation	For all $u\in V - \{s,t\},$ we require $\sum_{v\in V}f(v,u) = \sum_{v\in V}f(u,v)$ . When $(u,v)\notin E$ , there can be no flow from $u$ to $v$ , and $f(u,v)=0$ .

Med tanke på løsningen (den maksimale flyten), er dette helt ekvivalent. Problemet kommer da når man spør hva flyten er baklengs langs en kant $(u,v)$. Om man følger andreutgaven, blir svaret $-f(u,v)$, men om man følger tredjeutgaven blir svaret $0$.

Tanken er selvfølgelig at vi holder oss til nyeste utgave av læreboka, men det kan uansett være greit å vite om disse to ulike (ekvivalente) formuleringene – f.eks. om dere ser på gamle eksamensoppgaver.

Eksamen 2009, oppgave c, er innom dette, og LF gir to tillatte løsninger. Men hva er det egentlig som gjelder nå?

Om $f(u,v) = 3$ og $c(u, v) = 7$, er ikke da (om en vi aksepterer motgående flyt) $c_f(v,u) = 3$? Kan en ikke da oppheve $3$ og få $f(v,u) = 3$?

Jeg finner det også forvirrende at oppgaven spør om hvor mye en kan øke flyten fra $v$ til $u$ med, og hva flyten fra $v$ til $u$ da vil være, mens de to setningene i løsningsforslaget virker motsigende. «Det kan økes fra $-3$ til $0$» og «det kommer ann på om det går en kant fra $v$ til $u$, og hva kapasiteten er», og «det kan ikke gå noen flyt fra $v$ til $u$», men vi kan samtidig «øke den fra $0$ til $3$»?

Det som gjelder nå er det som står i nyeste versjon av læreboka (4. utgave), som tilsvarer den andre av de to versjonene over.

Du kan oppheve, men det betyr ikke at du kan få noe flyt den veien. Om du kun har en kant fra $u$ til $v$ og du har $f(u,v) = 3$ så kan du traversere fra $v$ til $u$ og oppheve $3$ enheter med flyt her. Det representeres ved at du har en kant $(v,u)$ med kapasitet $3$ i restnettet. Men du kan aldri få noe flyt fra $v$ til $u$, siden det ikke er noen kant der. Resultatet er det samme – det er bare måten man beskriver det på. Du kan fortsatt tenke deg at du øker flyten $f(v,u)$ fra $-3$ til $0$, men dette er altså ikke eksplisitt representert i formalismen lenger.