(a) You are organising some large-scale fund-raising event for a lot of charities together, and managed...

Transcribed Image Text:

(a) You are organising some large-scale fund-raising event for a lot of charities together, and managed to secure some major donors. Each donor agrees to donate some amount of money and each charity wants to raise a certain amount. However, because some donors care more about certain causes or because of their religious/political beliefs, some donors have specified that the money should only be donated to certain charities. An example is given in the tables below. Your task is to decide how much of each donor's money should go to which charity so that in total as much donations can be matched to the charities as possible. Donor D1 D2 D3 Amount to donate 40 90 100 Can donate to any (C1-C4) C1, C2, C3 only C2, C4 only Charities Amount required ន ខ ន ១ C2 C4 50 80 70 60 i. Describe how this problem can be transformed into a network flow problem. You should state clearly the set of vertices and edges and the edge capacities. You should describe the general transformation, not just for the specific example given in these tables. [4 marks] ii. Construct the transformed flow network for the example given in the tables. Then apply the Ford-Fulkerson algorithm to find the maximum flow in the network. You should show the residual network and augmenting path at each step. [12 marks] (a) You are organising some large-scale fund-raising event for a lot of charities together, and managed to secure some major donors. Each donor agrees to donate some amount of money and each charity wants to raise a certain amount. However, because some donors care more about certain causes or because of their religious/political beliefs, some donors have specified that the money should only be donated to certain charities. An example is given in the tables below. Your task is to decide how much of each donor's money should go to which charity so that in total as much donations can be matched to the charities as possible. Donor D1 D2 D3 Amount to donate 40 90 100 Can donate to any (C1-C4) C1, C2, C3 only C2, C4 only Charities Amount required ន ខ ន ១ C2 C4 50 80 70 60 i. Describe how this problem can be transformed into a network flow problem. You should state clearly the set of vertices and edges and the edge capacities. You should describe the general transformation, not just for the specific example given in these tables. [4 marks] ii. Construct the transformed flow network for the example given in the tables. Then apply the Ford-Fulkerson algorithm to find the maximum flow in the network. You should show the residual network and augmenting path at each step. [12 marks]

Answer rating: 100% (QA)

Step 1 i Transforming the problem into a network flow problem To transform the problem into a network flow problem we can represent each donor and charity as a node in a directed graph We can then cre... View the full answer