Mini #5, 15451 Fall 2010
       ========================

This mini is due via *email* to your TA, by 11:59pm Tuesday, Nov 2nd.
Please use the *exact* subject line "15-451 MINI #5" in your email.
As always make sure to include your name and Andrew ID.

Also, we prefer that you copy your answers directly into the email body, instead of including attachments. Thanks!


You are given a digraph on 6 vertices: s,a,b,c,d,t.
The graph has the following edges with the following capacity: (stated as (vertex-pair), capacity)

(s,a), 3
(s,b), 4
(a,c), 4
(b,a), 2
(b,c), 1
(c,d), 8
(c,t), 20
(d,b), 6
(d,t), 10


1. (3 pts) You are given the following flow: (stated as (vertex-pair), flow)
(s,a), 3
(s,b), 1
(a,c), 4
(b,a), 1
(c,d), 3
(c,t), 1
(d,t), 3

All other edges have flow = 0.

What are ALL the edges in the residual graph of this flow and what are their capacities?
Please list them in LEXICOGRAPHIC order (s<a<b<c<d<e<t), like they are listed here.
(Recall: edges of capacities 0 or below are NOT added to the residual graph.)


2. (4 pts) What is the value of the max-flow?

3. (3 pts) What is the min-cut? What is its value (specify participating edges)?