Hi there,

I had a bit of trouble solving these problems - I would appreciate your help!

1. Construct a flow network with n nodes that has 2^n-2 minimum cuts.

2. Consider the following two algorithms:

In the second algorithm the fattest means the largest bottleneck. The number of augmentations in Algorithm 1 is at most 2m*ceil(log_2(K)), where K is the maximum capacity of an edge. Deduce from this that the number of augmentations in Algorithm 2 is also at most 2m*ceil(log_2(K)).

Thank you!

Algorithm 1: Scaling max-flow Initially set f(e) := 0 for all edges e. Set to be max ce rounded down to a power of 2. While 1: - While there is an s, t-path P in Gf(): Augment the flow using P and update Gf( ). . Endwhile. . Endwhile. . Output f. Algorithm 1: Scaling max-flow Initially set f(e) := 0 for all edges e. Set to be max ce rounded down to a power of 2. While 1: - While there is an s, t-path P in Gf(): Augment the flow using P and update Gf( ). . Endwhile. . Endwhile. . Output f