- The Following Question Involves Maximum Flow Algorithms Namely Ford Fulkerson And Edmonds Karp Just Do Question 2 2 B 1 (103.72 KiB) Viewed 36 times
The following question involves maximum flow algorithms, namely Ford- Fulkerson and Edmonds-Karp. Just do question 2.2 b
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
The following question involves maximum flow algorithms, namely Ford- Fulkerson and Edmonds-Karp. Just do question 2.2 b
The following question involves maximum flow algorithms,namely Ford- Fulkerson and Edmonds-Karp. Just do question 2.2below. The yellow and green parts are hints. Explain the answeronly using words, numbers and/or pseudocode.
Question 2 There are k people living in a city, whose n suburbs and m roads can be represented by an unweighted directed graph. Every person is either slow or fast. Every night, • Each slow person can stay in the same suburb, or move along a road to an adjacent suburb. • Each fast person can stay in the same suburb, or move to any other suburb in the entire city. Over the last d days, you know how many people were located in each suburb. That is, for each day i and suburb j (where 1 ≤ i ≤ d and 1 ≤ j ≤ n), you know Pij, the number of people located in suburb j on day i. You are guaranteed that E-1 Pi,j = k for all i. 2.1 [10 marks] Design an algorithm which runs in O(d(n + m)) time and determines whether there could possibly be at least one slow person. Start with small cases such as d = 2, and then generalise. 2.2 [10 marks] Design an algorithm which runs in time polynomial in n, m, and d, and deter- mines the minimum possible number of fast people. • Has the wording in the third paragraph changed? Yes. This problem was updated on 03/07/22. • If there is no path from suburb i to suburb j, can a fast person move between them? Yes. Fast people essentially teleport.
Question 2 There are k people living in a city, whose n suburbs and m roads can be represented by an unweighted directed graph. Every person is either slow or fast. Every night, • Each slow person can stay in the same suburb, or move along a road to an adjacent suburb. • Each fast person can stay in the same suburb, or move to any other suburb in the entire city. Over the last d days, you know how many people were located in each suburb. That is, for each day i and suburb j (where 1 ≤ i ≤ d and 1 ≤ j ≤ n), you know Pij, the number of people located in suburb j on day i. You are guaranteed that E-1 Pi,j = k for all i. 2.1 [10 marks] Design an algorithm which runs in O(d(n + m)) time and determines whether there could possibly be at least one slow person. Start with small cases such as d = 2, and then generalise. 2.2 [10 marks] Design an algorithm which runs in time polynomial in n, m, and d, and deter- mines the minimum possible number of fast people. • Has the wording in the third paragraph changed? Yes. This problem was updated on 03/07/22. • If there is no path from suburb i to suburb j, can a fast person move between them? Yes. Fast people essentially teleport.