Optimisation on Networks

Question 1

source

Answer 1

γ(j,s)=0 for all j and γ(s,j)=/0 for some j

Question 2

sink

Answer 2

γ(d,j)=0 for all j and γ(j,d)=/0 for some j

Question 3

path

Answer 3

sequence of neighbouring arcs

Question 4

flow

Answer 4

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)

Question 5

saturated path under f

Answer 5

contains an arc where f=γ

Question 6

total flow from the source A(f)

Answer 6

sum over sources (sum over i (f(s,i)))

Question 7

cut

Answer 7

ordered pair of subsets, that partition all nodes and A contains source, B contains sink

Question 8

Maximal flow/minimal cut theorem

Answer 8

For maximal flow, there exists a cut st A(f)=min γ(Α,Β)