===========================================================================
CSC 373                     Homework Exercise 5                   Fall 2008
===========================================================================

Due: by 6pm on Tue 11 Nov
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure
that you use notation and terminology correctly, and that you explain and
justify what you are doing.  Marks *will* be deducted for incorrect or
ambiguous use of notation and terminology, and for making incorrect,
unjustified, ambiguous, or vague claims in your solutions.


1.  Find a cut with minimum capacity in the network N = (V,E) with vertex
    set V = {s,a,b,c,d,e,f,t} and edge set described below.  Justify that
    your cut's capacity is minimum, and show your work (i.e., show the
    steps you followed in order to determine the cut).

         edge capacity
        ----- --------
        (s,a)    11
        (s,c)    16
        (s,d)     4
        (a,b)    18
        (a,d)     6
        (a,f)     3
        (b,e)     1
        (b,f)     8
        (c,b)    32
        (c,e)     2
        (d,f)    10
        (d,t)     1
        (e,c)     3
        (e,t)     2
        (f,b)     9
        (f,e)    12
        (f,t)    24


2.  Consider a flow network in which each vertex has a capacity, in
    addition to each edge, i.e., a network N = (V,E) with a single source
    s (- V, a single sink t (- V, edge capacities c(e) >=0 for all e (- E
    and vertex capacities c(v) >= 0 for all v (- V (including s and t).

    For such a network, the capacity constraint is extended to include
    vertices: for each vertex v (- V, f^{in}(v), f^{out}(v) <= c(v), i.e.,
    the total flow into or out of any vertex cannot exceed the capacity of
    that vertex.

    Explain how to determine a flow with maximum value in such a network,
    and justify that your algorithm works properly.