Use the techniques of this chapter to find a maximum matching from \(V_1\) to \(V_2\) in the graph shown in Figure 14.11. The vertices on the bottom are the set \(V_1\text{,}\) while the vertices on the top are the set \(V_2\text{.}\) If you cannot find a matching that saturates all of the vertices in \(V_1\text{,}\) explain why.
Figure14.11.Is there a matching saturating \(V_1\text{?}\)
2.
Use the techniques of this chapter to find a maximum matching from \(V_1\) to \(V_2\) in the graph shown in Figure 14.12. The vertices on the bottom are the set \(V_1\text{,}\) while the vertices on the top are the set \(V_2\text{.}\) If you cannot find a matching that saturates all of the vertices in \(V_1\text{,}\) explain why.
Figure14.12.Is there a matching saturating \(V_1\text{?}\)
3.
Students are preparing to do final projects for an applied combinatorics course. The five possible topics for their final projects are graph algorithms, posets, induction, graph theory, and generating functions. There are five students in the class, and they have each given their professor the list of topics on which they are willing to do their project. Alice is interested in posets or graphs. Bob would be willing to do his project on graph algorithms, posets, or induction. Carlos will only consider posets or graphs. Dave likes generating functions and induction. Yolanda wants to do her project on either graphs or posets. To prevent unauthorized collaboration, the professor does not want to have two students work on the same topic. Is it possible to assign each student a topic from the lists above so that no two students work on the same project? If so, find such an assignment. If not, find an assignment that maximizes the number of students who have assignments from their lists and explain why you cannot satisfy all the students’ requests.
4.
Seven colleges and universities are competing to recruit six high school football players to play for their varsity teams. Each school is only allowed to sign one more player, and each player is only allowed to commit to a single school. The table below lists the seven institutions and the students they are trying to recruit, have been admitted, and are also interested in playing for that school. (There’s no point in assigning a school a player who cannot meet academic requirements or doesn’t want to be part of that team.) The players are identified by the integers \(1\) through \(6\text{.}\) Find a way of assigning the players to the schools that maximizes the number of schools who sign one of the six players.
School
Player numbers
Boston College
1, 3, 4
Clemson University
1, 3, 4, 6
Georgia Institute of Technology
2, 6
University of Georgia
None interested
University of Maryland
2, 3, 5
University of North Carolina
1, 2, 5
Virginia Polytechnic Institute and State University
1, 2, 5, 6
5.
The questions in this exercise refer to the network diagram in Figure 14.13. This network corresponds to a poset \(\bfP\text{.}\) As usual, all capacities are assumed to be \(1\text{,}\) and all edges are directed upward. Answer the following questions about \(\bfP\)without drawing the diagram of the poset.
Which element(s) are greater than \(x_1\) in \(\bfP\text{?}\)
Which element(s) are less than \(x_5\) in \(\bfP\text{?}\)
Which element(s) are comparable with \(x_6\) in \(\bfP\text{?}\)
List the maximal elements of \(\bfP\text{.}\)
List the minimal elements of \(\bfP\text{.}\)
Figure14.13.The network corresponding to a poset
6.
Draw the diagram of the poset that corresponds to the network in Figure 14.13.
7.
Use the methods developed in this chapter to find the width \(w\) of the poset corresponding to the network in Figure 14.13. Also find an antichain of size \(w\) and a partition into \(w\) chains.
8.
In Figure 14.14 we show a poset \(\bfP\) and a network used to find a chain partition of \(\bfP\text{.}\) (All edges in the network have a capacity of \(1\) and are directed from bottom to top. The bold edges currently carry a flow of \(1\text{.}\)) Using the network, find the width \(w\) of \(\bfP\text{,}\) a partition of \(\bfP\) into \(w\) chains, and an antichain with \(w\) elements.
Figure14.14.A poset and the corresponding network diagram
9.
Draw the network corresponding to the poset \(\bfP\) shown in Figure 14.15. Use the network to find the width \(w\) of \(\bfP\text{,}\) a partition into \(w\) chains, and an antichain of size \(w\text{.}\)
