1
Q
source
A
γ(j,s)=0 for all j and γ(s,j)=/0 for some j
2
Q
sink
A
γ(d,j)=0 for all j and γ(j,d)=/0 for some j
3
Q
path
A
sequence of neighbouring arcs
4
Q
flow
A
function satisfying:
f(i,j) is less or equal to γ(i,j)
f(i,j)=-f(j,i)
Sum of j of f(i,j) is equal to sum over j of f(j,i) for all i (except sinks and sources)
5
Q
saturated path under f
A
contains an arc where f=γ
6
Q
total flow from the source A(f)
A
sum over sources (sum over i (f(s,i)))
7
Q
cut
A
ordered pair of subsets, that partition all nodes and A contains source, B contains sink
8
Q
Maximal flow/minimal cut theorem
A
For maximal flow, there exists a cut st A(f)=min γ(Α,Β)
