The following question involves maximum flowalgorithms, namely Ford- Fulkerson andEdmonds-Karp.
Just do question 3.1 below. The yellow and green partsare hints. Explain the answer only using words, numbers and/orpseudocode.
The Following Question Involves Maximum Flow Algorithms Namely Ford Fulkerson And Edmonds Karp Just Do Question 3 1 B 1 (62.93 KiB) Viewed 57 times
There n boys and n girls at a party. Whenever a song starts, they will form exactly n pairs to dance. No boy will dance with the same girl twice. Some pairs of boys and girls like each other, and all other pairs of boys and girls dislike each other. Every boy will dance with at most k girls that he dislikes, and each girl will dance with at most k boys that she dislikes, where k<n. As the DJ, your job is to determine the maximum number of songs you can play, such that it is possible for pairs to be formed for all songs according to the above requirements. Design an algorithm which achieves this and runs in time polynomial in n: 3.1 [10 marks] for k For a fixed value of s, can a total of s songs be played? = 0. 3.2 [10 marks] for arbitrary k. You may choose to skip 3.1, in which case we will mark your submission for 3.2 as if it was submitted for 3.1 also. Is the value of k the same for everyone at the party? Yes.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!