Homework 6

Details

1. (6+4+2 pts) Apply the Ford-Fulkerson algorithm to find the maximum flow of the following network.
   Do not forget to:
   1. Show all of the intermediate steps (copy this graph into your file and/or print it multiple times to make it easier!)
   2. Draw the maximum flow and give the value of the maximum flow.
   3. Specify the minimum cut (i.e. give the set X).
2. (6 pts) IDAA 10.2.10 (page 372).
   Explain how to construct the appropriate graph and explain what a maximum flow tells us about the answer to the question.
   Make sure you clearly explain your solution!
3. (6 pts) IDAA 10.3.1 (page 378)
   Make sure to fully justify your answer.
4. (6 pts) IDAA 10.3.10 (page 380)
   To clarify, it is looking for a tiling in which the lower left and upper right squares are empty, but the rest of the board is covered. Looking at a picture of a chess board might help. Make sure to prove your answer.