Exercise 1

a) What is the maximum flow problem?
    To use the least amounts of nodes from start to end.
    To let the flow from s to t be maximal
    To let the flow between each node be maximal.
    To maintain/sustain the flow.

b) What does "skew-symmetry" mean?
    Flow into a node is equal to the flow from the node
    Flow over an edge is equal to negative flow in the opposite direction
    Flow into the terminal(t) is equal to the flow from the source(s)

c) Is this a flow network?
    Yes
    No

d) Is this a flow network?
    Yes
    No

e) Is this a flow network?
    Yes
    No


This task shall give a basic introduction to how flow networks operate. Note that if an edge reads 10, it means the same as 0/10. Negative flow is not listed, so if you have an edge with label 6/16, there will also be an edge -6/0 in the opposite direction.

f) What does the notation 1/5 between node a and f mean?
    c(a,f) = 1, f(a,f) = 5 ?
    c(a,f) = 5, f(a,f) = 1 ?


g) Is the flow sustained/maintained in this flow diagram?
    Yes
    No


h) What is f(a,e) in this flow network?
    7
    -7
    3
    -3





i) Is the flow sustained/maintained in this flow diagram?
    Yes
    No

j) Is the flow sustained/maintained in this flow diagram?
    Yes
    No

k) Is the flow sustained/maintained in this flow diagram?
    Yes
    No
    
l) What is the residual capacity between node e and T?
    c(e,T)=1, c(T,e)=3 ? 
    c(e,T)=3, c(T,e)=1 ? 
    c(e,T)=1, c(T,e)=2 ? 
    c(e,T)=2, c(T,e)=1 ?


m) Which of these paths is an "augmenting-path"?
    s,d,f,t ? 
    b,c,f,t ? 
    s,a,f,t ? 
    s,b,c,g,t ?


n) Use Ford-Fulkerson’s method and find maximal flow between s and t. What is max |f|?
32 23 20 26 



Exercise 2

What is the maximal flow between s and t in this graph?
    6
    9
    49
    85
    122



Exercise 3

Let G=(V,E) be a flow network where each line has a capacity 1, s and t are source and sink respectively.
Assume for both a) and b), that maximal flow is already found by the means of a flow algorithm A(s,t). 

a) Assume that we add a new line with capacity 1 between two arbitrary nodes u and v in G.  How can we most efficiently find a new (perhaps higher) flow in G? Note that the new flow in all edges is to be found.
    Run A(s,t) only once.
    Maximal flow will automatically increase by 1.
    Max flow will not increase at all.
    Run A(s,t) once per node. 


b) Assume that we remove an edge (u,v) with flow 1 between to arbitrary nodes u and v in G. How can we most efficiently find a new (possibly lower) flow in G? Here too the flow in all existing edges is to be found.
    Run A(s,t) only once.
    Run A(s,u), then A(v,t) and finally A(s,t).
    Run A(t,v), then A(u,s) and finally A(s,t).
    Run A(s,t) once per node.