1. Prove that if all edge capacities are rational, Ford-Fulkerson halts. 2. Solve the recurrence a_{n+2} = a_n-a_{n+1 } Use the initial conditions a 0-1, a 1 = r where r is the root of the characteristic polynomial that has absolute value less than I Let S= sum-{na0P(n=infinity} a_n 3. Consider the directed graph G (VE) with and edges (s, x-i for all i, (y1) for allj,(yj , yj), (x-iy.J ), (y-i,zj)for all iwj, and edges ei =(x-i , yj ) for i=1,2,3,4. Edges e_i have capacities a (1-1) (the a j are the solutions of the recurrence of part 2). All other arcs have capacity S Design a strategy that finds paths in the graph G-(Lk)(and corresponding increasing flows Lk such that Lk = Prove your strategy by induction. This yields a flow which is the sum of the a i 4. The strategy above yields an infinite sequanece of augmenting flows. Compute the limit (the sum of the series) and compare it with the maximum flow