Question
Data Structures and Algorithms:
Please use the words, diagrams, and mathematical symbols to state the concepts you want to express.
Thanks for your answers.
(25 points) We are given a set of C classes and R classtooms and we would like to assign as many classes to classrooms as possible. Due to equipment constraint not every class can be assigned to every classroom. Instead we will be given a set M of pairs (c,T), and each pair indicates that class c can be assigned to classroom r. In addition, a class, if assigned, will be assigned to a unique classroom. Therefore it is possible that we cannot assign every class to a unique classroom. Our goal is to assign as many classes to classrooms as possible. 'We consider the following example. Let a lower case letter indicate a class and a positive integer indicate the index of a classroom. Let M = {(a, 1), (a, 2), (b, 2), which means class a can be assigned to classroom 1 and 2, but class b can only be assigned to classroom 2. Now given the set M, please find the maximum number of classes that can be assigned to classrooms. In the previous example the answer is 2 since we can assign class a to classroom 1 and b to classroom 2. We can use Ford-Fulkerson method to solve this problem. Basically the Ford-Fulkerson method initializes the flow to 0, then repeatedly finds an augmenting path p, and adjusts the capacity along the path found on the residual network, until no augmenting path can be found. (a) (10 points) Now assume that Ford-Fulkerson method can find the maximum fiow in a network, hovw do we convert our problem into a network flow problem so that we can use Ford-Fulkerson method to solve it? (b) (15 points) Prove that Ford-Fulkerson method can correctly solve our problem by your conversion. To be more specific, is it true that any maximum flow will give you a correct answer for the classroom problem? Also is it true that the answer from the Ford-Fulkerson method will give you a correct answer in our classroom problem?
Explanation / Answer
(a) We can converte this problem to network flow problem as follow:
The class will the node of the network.
If two class can be assigned the a same class room than there will be an edge connecting them.
The cappacity of the edge should be fixed to 1 only.
The flow capacity of the network is total number of differen class room index. i.e for example given in your problem capacity c=2.
The source node is the node with minimum degree and sink node is the node with second minimum degree.
(b) No any maximum flow will not give the correct answer.
The answer from the Ford-fullkerson method will give a correct answer.
