I need help on a CSE 3500 assignment, third year computer science course called Algorithms and Complexity. There are 3 questions. I need very detailed answers so that I can learn the material. See attached file.

 

CSE 3500Algorithms and ComplexityDue April 19, 2016Homework 9No collaboration with others, nor use of material other than the textbook and class notes, areallowed. Enjoy!1. For the following graph, find the maximum flow and minimum cut by applying Ford-Fulkerson byhand. Show the intermediate graphs and residual graphs.2. Suppose you are given a flow network where each edge has the same capacity, that is, a directedgraphG= (V,E)with a source nodesand sink nodet, such thatce=jfor alle∈E, wherejis aninteger constant greater than zero. You can reduce the maximum s-t flow by removing edges.Givenk<|E|, find thekedges whose removal from the graph reduces the maximum s-t flow themost. That is, describe the algorithm that takes a flow networkG= (V,E)and a number k, andreturns the set of edgesE0such thatE0⊂Eand|E0|=k, and the maximum s-t flow in(V,E-E0)is as small as possible.Your algorithm should be polynomial in|V|+|E|, the number of vertices and edges in the graph.You can assume you have the Ford-Fulkerson algorithm to build on.3. LetG= (V,E)be a flow network with sources, sinktand integer capacities. Suppose that we aregiven a maximum flow inG.(a) Suppose that the capacity of a single edge(u,v)∈Eis increased by 1. Give anO(|V|+|E|)time algorithm to update the maximum flow.(b) Suppose that the capacity of a single edge(u,v)∈Eis decreased by 1. Give anO(|V|+|E|)time algorithm to update the maximum flow.1

Attachments:

• 1495765107-CSE 3500 - ProblemSet9.pdf