Homework 6

1.
             8
        a ------> b
   10 ^ ^         | \3     
    /    \       /   v
  s      2\    4/     t
    \      \   v     ^
      -----> c -----/
       5          6 

a)  (remaining flow on forward edge) / (flow on back edge)

             6/2
        a ------> b
   10 ^ ^         | \1/2     
    /    \       /   v
  s    0/2\    4/     t
    \      \   v     ^
      -----> c -----/
       3/2          6 

b) s-c-t

c) s-a-b-c-t

d)

             4
        a ------> b
   4  ^ ^         | \3     
    /    \       /   v
  s      0\    1/     t  Max Flow = 9
    \      \   v     ^
      -----> c -----/
       5          6 


             4
 \      a ------> b
   4  ^ ^         | \3     
    /\   \       /   v
  s   |  0\    1/     t
    \/     \   v     ^
   /  -----> c -----/
  /    5          6 

Min cut = 9


2.
   A = Athletics  M = Mariners  R = Rangers  XY = Game between Team X and Team Y

                 1   
          AM  ---  A
       1/    \ / 1   \
      /      / \       \2
    /  1   /     \1   2 \
  s  -- AR          M --- t
    \      \      /1    /
     1\      \ /      2/
        \   /   \1    /
          RM  ---  R
                 1

a)

                 1   
          AM  ---  A
       1/    \ / 0   \
      /      / \       \1
    /  1   /     \0   1 \
  s  -- AR          M --- t
    \      \      /1    /
     1\      \ /      1/
        \   /   \1    /
          RM  ---  R
                 0

b)  It is still possible for the Angels to win