1 Network Flow Consider the flow network depicted below where each directed edge is labeled with its capacity We are applying the Ford Fulkerson algorithm to determine the maximum flow The first augmenting path chosen is s a c d t The second augmenting path chosen is s a b c d t Homework 4 CSCI570 Fall 2024 Due Nov 3 2024 s 1 1 t 2 4 a c 3 3 3 b d 4 3 a Draw the residual networks after each of these two augmentation steps following the order given b List all possible augmenting paths that could be selected for the third augmentation step c Determine the value of the maximum flow in this network above Solution a The residual network after the first augmentation step s 1 1 t 1 1 4 a c 3 2 1 3 b d 4 2 1 The residual network after the second augmentation step 1 s 1 1 t a c 2 1 1 2 2 1 2 4 b d 4 1 2 b s c a b t s c b t s c d b t and s c d t c The max flow is 5 Rubrics 10 points 4 pts Completely correct residual networks 2 pts for each of the two augmentation steps 4 pts List all correct possible augmenting paths 1 pt for every path missing 2 pts Correct max flow value 2 Network Flow In the year 3024 humanity has begun colonizing distant planets Your task is to design a system for allocating colonists to habitable zones on a newly discovered planet Consider a group of n colonists c1 c2 cn each with specific x y coordinates on the planet s surface There are k habitable zones h1 h2 hk also defined by their x y coordinates Your mission is to assign each colonist to exactly one habitable zone subject to the following constraints 1 Oxygen Limit due to the planet s thin atmosphere colonists can only be assigned to habitable zones within a maximum distance of R units 2 Resource Capacity Each habitable zone has limited resources and can support no more than L colonists a Describe how to construct a flow network to model this problem Clearly explain what each node and edge in your network represents and how the capacities are assigned b Make a claim regarding a valid assignment of colonists to habitable zones Prove the claim in both directions Solution a Construct the following network connect each colonist ci to a habitable zone hj if it is within a distance of R units Assign capacity 1 to those edges Let s be a source vertex and t be a sink vertex For every colonist vertex add an edge s ci of capacity 1 For every habitable zone add an edge hj t of capacity L b Claim the problem has a solution if and only if the network has a max flow of value n Forward Proof Assume that the problem has a solution That is every colonist is connected to a habitable zone Therefore we can push a flow of 1 unit from the source to each colonist Then assign a flow of 1 unit between each colonist and its corresponding habitable zone Finally assign a flow value equals to the number of colonists from that habitable zone to the sink It follows that the max flow is n Backward Proof Assume that there is a max flow of value n Then each colonist will get a flow of 1 unit so that all colonists are assigned to habitable zones By the design of the network the two constraints are satisfied Therefore the problem has a solution 2 Rubrics 10 points 5 pts Correct construction of the flow network 1 pt Correct claim 2 pts Correct forward proof 2 pts Correct backward proof 3 Network Flow A tourist group needs to convert all of their USD into various international curren cies There are n tourists t1 t2 tn and m currencies c1 c2 cm Each tourist tk has Fk Dollars to convert For each currency cj the bank can convert at most Bj Dollars to cj Tourist tk is willing to trade at most Skj of their Dollars for currency cj For example a tourist with 1000 dollars might be willing to convert up to 300 of their USD for Indian Rupees up to 500 of their USD for Japanese Yen and up to 400 of their USD for Euros Assume that all tourists give their requests to the bank at the same time a Design an algorithm that the bank can use to determine whether all requests can be satisfied To do this construct and draw a network flow graph with appropriate source and sink nodes and edge capacities b Prove your algorithm is correct by making an if and only if claim and proving it in both directions Solution a We aim to solve the problem by constructing a network flow graph and then running a Network Flow Algorithm such as Ford Fulkerson or Edmonds Karp to compute the maximum flow value Insert two new vertices the source node S and the sink node T Connect each tourist tk with the source node S and assign an edge weight equal to Fk where Fk represents the maximum USD that tourist tk can exchange Connect each tourist tk to all available currencies cj with each edge having a weight Skj which is the limit of USD that tourist tk can exchange for a particular currency cj Connect each currency cj to the sink node T with edge weight Bj which represents the maximum amount of currency cj that the bank can convert from USD We can run an efficient Network Flow Algorithm e g Edmonds Karp on the constructed graph k Fk then all requests can be satisfied In this case the flow on each edge tk cj represents the amount that tourist tk exchanges into currency cj from source S to sink T If the max flow value equals cid 80 satisfying all constraints if and only if the max flow value on the constructed graph is cid 80 b Claim The problem has a solution i e all tourists can exchange their specified USD while k Fk We will prove this claim in both directions Forward Direction is cid 80 Assume there is a valid assignment such that the bank can satisfy all tourists requests for conversion while satisfying all constraints We aim to prove that the max flow value k Fk Suppose in this assignment each tourist tk is converting xkj amount into each currency cj Then in the constructed network we can send xkj units of flow along each path S tk cj T This satisfies both flow conservation and non negativity The flow along each edge S tk is exactly Fk since this equals the total amount of USD that tk exchanges The flow along each edge tk cj is at most Skj as that is the maximum amount tk is willing to convert into currency cj Additionally the flow along each edge cj T is at most Bj …