15.093 - Recitation 6 October 23, 2009 1 BT Exercise 7.1 (Caterer Problem) Solution Construct the n/w as follows: For each day i, create two nodes as follows: • node ci for clean tablecloths, with supply ri • node di for dirty tablecloths, with demand ri Create a node s for the source of new tablecloths. Each node ci can: • receive new tablecloths from purchasing: arcs (s, ci ) with arc cost p and unlimited capacity. • receive “fast” laundered tablecloths from n days ago (or longer): arcs (di−n−j , ci ) if i > n + j with arc cost f and unlimited capacity • receive “slow” laundered tablecloths from m days ago (or longer): arcs (di−m−j , ci ) if i > m + j with arc cost g and unlimited capacity For each node di , create arcs (di , s) with zero cost and unlimited capacity, representing tablecloths which are not laundered and used again. 2 BT Exercise 7.3 (Tournament Problem) Solution We introduce nodes T1 , ..., Tn that correspond to the diﬀerent teams. These are the supply nodes and node Ti has a supply of xi , the total number of games won by team i. For every unordered pair i, j of teams, we introduce a node Gij . These are demand nodes, with demand k, the total number of games played between these two teams. Since 1 the �n total number of games must be equal to the total number of wins, we assume that i=1 xi = n(n − 1)/2. There are two arcs that come into a node Gij ; one from Ti and one from Tj . The ﬂow from Ti to Gij represents the total number of games between teams i and j that was won by team i. The above constructed n/w ﬂow problem is feasible if and only if the vector (x1 , ..., xn ) belongs to the set of possible outcome vectors. 3 BT Exercise 7.23 (Marriage Problem) Solution A source node s, a node for each man, an arc connecting the source node with each man, capacity of 1 unit. A sink node t, a node for each woman, an arc connecting each woman node with the sink node, capacity of 1 unit. Two nodes for each broker, which are connected with each other by an arc with the capacity of bi . One in these two nodes is connected with man nodes that the broker knows while the other node connects to all woman nodes that the broker knows. 2