Question

1. Saving lives in a natural disaster Due to large scale natural disaster in a region, paramedics have identified a set of n injured people, P₁, P₂,… P_n, distributed across the region who need to be rushed to hospitals. There are k hospitals in the region, H₁, H₂,… H_k, and each person needs to be taken to a hospital within 30 minutes travel time to the hospital. You know the travel time for each person to each hospital. Some people will have a choice of hospitals to go to. You want to work out whether or not there is a solution where each hospital receives at most én/kù people.
   1. Determine a flow graph that represents this problem. That is specify its vertices and edge

Types of vertices:and with what they represent

Types of edges along with what they represent and their capacity

2. explain how the max flow algorithm solves this problem. That is how does the result of running the algorithm give us information about whether or not the problem is solved and what we can determine from the flows on the graph.

java

Answer 1

Network is built by taking a node pa for each patient a and node ho for each hospital o. Now, there is a node with an edge (pa, ho) of capacity 1 as it takes 30 minutes for the patient a to travel to the hospital o, as per the given question.

There is a super-source, so which is connected to each patient node by edge (so,pa) of capacity 1. And there is super-sink, sk to which each hospital node is connected by edge of capacity (n/k).

It is possible that all the patients are sent to the hospital if the flow of patients is so-sk.

We can send one unit of flow from so to sk along each of the paths so,pa,ho,sk, in which paietnt is a and hospital is o.

We need to ensure that no hospital is overloaded, and each patient a is sent to hospital o if the edge (pa, ho) carries one unit of flow. No hospital can have more than n/k patients.

This graph will have O(n+k) nodes and O (nk) edges. Hence, running time will be O(n2) (this is O(n square)), using Ford- Fulkerson algorithm. 'Ford- Fulkerson' is the greedy algorithm that calculates maximum flow in the flow network i.e: how much "flow" can be processed via a network at a given time.