Maxflow and Mincut Help Center

Learn more

Warning: The hard deadline has passed. You can attempt it, but you will not get credit for it. You are welcome to try it as a learning exercise.

To specify an array or sequence of values in an answer, separate the values in
the sequence by whitespace. For example, if the question asks for the first
ten powers of two (starting at 1), then the following answer is acceptable:

     1 2 4 8 16 32 64 128 256 512

If you wish to discuss a particular question and answer in the forums, please
post the entire question and answer, including the seed (which can be used by
the course staff to uniquely identify the question) and the explanation (which
contains the correct answer).

Question 1

(seed = 722652)
Suppose that you are computing a max flow from the source vertex A to the
sink vertex J in the flow network given below:

    edge   flow  /  capacity
    ------------------------
    A->B     15  /  15
    A->F     12  /  17
    A->G     11  /  11
    B->C     10  /  19
    B->G      5  /   5
    C->D     19  /  19
    C->G      0  /   7
    D->E      5  /   5
    D->I     16  /  16
    D->J      3  /  12
    E->J      5  /  14
    F->G     12  /  16
    G->H     28  /  28
    H->C      9  /  11
    H->D      5  /  17
    H->I     14  /  14
    I->J     30  /  31


Here is a graphical representation of the same flow network:                                                                                          


      (A)------15/15----->(B)------10/19----->(C)------19/19----->(D)-------5/5------>(E) 
       |\                  |                  /^                  ^|\                  |  
       | \                 |                 / |                 / | \                 |  
       |  \                |                /  |                /  |  \                |  
       |   \               |               /   |               /   |   \               |  
       |    \              |              /    |              /    |    \              |  
       |     \             |             /     |             /     |     \             |  
       |      \            |            /      |            /      |      \            |  
       |       \           |           /       |           /       |       \           |  
       |        \          |          /        |          /        |        \          |  
     12/17     11/11      5/5       0/7       9/11      5/17     16/16      3/12      5/14
       |          \        |        /          |        /          |          \        |  
       |           \       |       /           |       /           |           \       |  
       |            \      |      /            |      /            |            \      |  
       |             \     |     /             |     /             |             \     |  
       |              \    |    /              |    /              |              \    |  
       |               \   |   /               |   /               |               \   |  
       |                \  |  /                |  /                |                \  |  
       |                 \ | /                 | /                 |                 \ |  
       v                  vvv                  |/                  v                  vv  
      (F)------12/16----->(G)------28/28----->(H)------14/14----->(I)------30/31----->(J) 



Starting from the given flow (of value 38), give the sequence of vertices in the
next (and final) augmenting path discovered by the Ford-Fulkerson algorithm.

Question 2

(seed = 929334)
Consider the flow network with 10 vertices and 17 edges:

    edge   flow  /  capacity
    ------------------------
    A->B      6  /   6
    A->F      3  /   6
    A->G      0  /   7
    H->B      3  /   9
    B->G      4  /  12
    B->C      5  /   5
    C->D      5  /   8
    C->H      0  /  11
    D->H      0  /   9
    D->J      5  /   5
    D->I      0  /   8
    D->E      0  /  10
    E->J      0  /   7
    F->G      3  /   7
    G->H      7  /   7
    H->I      4  /   4
    I->J      4  /   6


Here is a graphical representation of the same flow network:                                                                                          


      (A)-------6/6------>(B)-------5/5------>(C)-------5/8------>(D)-------0/10----->(E) 
       |\                  |^                  |                  /|\                  |  
       | \                 | \                 |                 / | \                 |  
       |  \                |  \                |                /  |  \                |  
       |   \               |   \               |               /   |   \               |  
       |    \              |    \              |              /    |    \              |  
       |     \             |     \             |             /     |     \             |  
       |      \            |      \            |            /      |      \            |  
       |       \           |       \           |           /       |       \           |  
       |        \          |        \          |          /        |        \          |  
      3/6       0/7       4/12      3/9       0/11      0/9       0/8       5/5       0/7 
       |          \        |          \        |        /          |          \        |  
       |           \       |           \       |       /           |           \       |  
       |            \      |            \      |      /            |            \      |  
       |             \     |             \     |     /             |             \     |  
       |              \    |              \    |    /              |              \    |  
       |               \   |               \   |   /               |               \   |  
       |                \  |                \  |  /                |                \  |  
       |                 \ |                 \ | /                 |                 \ |  
       v                  vv                  \vv                  v                  vv  
      (F)-------3/7------>(G)-------7/7------>(H)-------4/4------>(I)-------4/6------>(J) 




The flow given above is a maxflow from A to J. What is the corresponding mincut?
List the vertices on the s side of mincut in alphabetical order.

Question 3

(seed = 731167)
Which of the following statements about maxflow and mincut are guaranteed to be true in any flow network G? Check all that apply. As usual, we use the term maxflow to refer to an st-maxflow and mincut to refer to an st-mincut and we assume the network is directed.
    
You cannot submit your work until you agree to the Honor Code. Thanks!