1. A town has r residents R.R....R: q clubs CCC; and p political parties P.P....P. Each...

  

Transcribed Image Text:

1. A town has r residents R₁.R....R: q clubs CCC; and p political parties P.P....P. Each resident is a member of at least one club and can belong to exactly one political party. Each club must nominate one of its members to represent it on the town's governing council so that the number of council members belonging to the political party Pk is at most uk. Is it possible to find a council that satisfies this 'balancing' property? Illustrate this formulation with an example (e.g. r- 5.q=3, p=2). 2. Let G=(N,A) be a directed graph with two specified nodes s and t. Your task is to find out if there exist at least 2 directed paths from s to t which do not share any arc. Formulate this problem as a maximum flow problem. 3. Several families go out to dinner together. To increase their social interaction, they would like to sit at tables so that no two members of the same family are at the same table. Show how to formulate finding a seating arrangement that meets this objective as a maximum flow problem. Assume that there are 4 families and 3 tables. The number of members of families and table capacities are given in the table below. Number 1 2 3 4 Number of Family Members 3 5 2 4 Table Capacity 5 7 3 4. Find the maximum flow from source to sink in each network. Find a cut in the network whose capacity equals the maximum flow in the network. Also, set up an LP that could be used to determine the maximum flow in the network. 50 2 2 2 5. The Hatfields, Montagues, McCoys, and Capulets are going on their annual family picnic. Four cars are available to transport the families to the picnic. The cars can carry the following number of people: car 1, four; car 2, three; car 3, three; and car 4, four. There are four people in each family, and no car can carry more than two people from any one family. Formulate the problem of transporting the maximum possible number of people to the picnic as a maximum-flow problem. 6. Suppose that a maximum flow network contains a node, other than the source node, with no incoming arc. Can we delete this node without affecting the maximum flow value? Similarly, can we delete a node, other than the sink node, with no outgoing arc? 7. Which of the following claims are true and which are false. Justify your answer either by giving a proof or by constructing a counterexample. a) If x is a maximum flow, either xij = 0 or xji =0 for every are (i; j) in A. b) Any network always has a max flow x for which, for every are (i, j) in A, either xij=0 or xji = 0. c) If all arcs in a network have different capacities, the network has a unique minimum cut. d) If we multiply each are capacity by a positive number A, the minimum cut remains un- changed. e) If we add a positive number A to each are capacity, the minimum cut remains unchanged. 8. A commander is located at node p in an undirected communication network G and his subordinates are located at nodes by the set S. Let uij be the effort required to eliminate arc (i,j) from the network. The problem is to determine the minimal effort required to block all the communications between the commander and his subordinates. How can you solve this problem? 1. A town has r residents R₁.R....R: q clubs CCC; and p political parties P.P....P. Each resident is a member of at least one club and can belong to exactly one political party. Each club must nominate one of its members to represent it on the town's governing council so that the number of council members belonging to the political party Pk is at most uk. Is it possible to find a council that satisfies this 'balancing' property? Illustrate this formulation with an example (e.g. r- 5.q=3, p=2). 2. Let G=(N,A) be a directed graph with two specified nodes s and t. Your task is to find out if there exist at least 2 directed paths from s to t which do not share any arc. Formulate this problem as a maximum flow problem. 3. Several families go out to dinner together. To increase their social interaction, they would like to sit at tables so that no two members of the same family are at the same table. Show how to formulate finding a seating arrangement that meets this objective as a maximum flow problem. Assume that there are 4 families and 3 tables. The number of members of families and table capacities are given in the table below. Number 1 2 3 4 Number of Family Members 3 5 2 4 Table Capacity 5 7 3 4. Find the maximum flow from source to sink in each network. Find a cut in the network whose capacity equals the maximum flow in the network. Also, set up an LP that could be used to determine the maximum flow in the network. 50 2 2 2 5. The Hatfields, Montagues, McCoys, and Capulets are going on their annual family picnic. Four cars are available to transport the families to the picnic. The cars can carry the following number of people: car 1, four; car 2, three; car 3, three; and car 4, four. There are four people in each family, and no car can carry more than two people from any one family. Formulate the problem of transporting the maximum possible number of people to the picnic as a maximum-flow problem. 6. Suppose that a maximum flow network contains a node, other than the source node, with no incoming arc. Can we delete this node without affecting the maximum flow value? Similarly, can we delete a node, other than the sink node, with no outgoing arc? 7. Which of the following claims are true and which are false. Justify your answer either by giving a proof or by constructing a counterexample. a) If x is a maximum flow, either xij = 0 or xji =0 for every are (i; j) in A. b) Any network always has a max flow x for which, for every are (i, j) in A, either xij=0 or xji = 0. c) If all arcs in a network have different capacities, the network has a unique minimum cut. d) If we multiply each are capacity by a positive number A, the minimum cut remains un- changed. e) If we add a positive number A to each are capacity, the minimum cut remains unchanged. 8. A commander is located at node p in an undirected communication network G and his subordinates are located at nodes by the set S. Let uij be the effort required to eliminate arc (i,j) from the network. The problem is to determine the minimal effort required to block all the communications between the commander and his subordinates. How can you solve this problem?