9. Recall from Example 1 in Section 1.1 that a graph is bipartite if the vertices...

 

Transcribed Image Text:

9. Recall from Example 1 in Section 1.1 that a graph is bipartite if the vertices can be divided into two sets; for convenience call them blue vertices and red vertices, such that every edge connects a blue and a red vertex. (a) Show that if a connected bipartite graph has a Hamilton circuit, then the numbers of red and blue vertices must be equal. Further, show that if a bipartite graph has an odd number of vertices, then it has no Hamilton circuit. (b) Show that if a connected bipartite graph has a Hamilton path, then the num- bers of reds and blues can differ by at most one. Example 1: Matching Suppose that we have five people A, B, C, D, E and five jobs a, b, c, d, e, and that various people are qualified for various jobs. The problem is to find a feasible one- to-one matching of people to jobs, or to show that no such matching can exist. We A B с De W E a b d 1.1 Graph Models 5 Figure 1.2 can represent this situation by a graph with vertices for each person and for each job, with edges joining people with jobs for which they are qualified. Does there exist a feasible matching of people to jobs for the graph in Figure 1.2? The answer is no. The reason can be found by considering people A, B, and D. These three people as a set are collectively qualified for only two jobs, c and d. Hence there is no feasible matching possible for these three people, much less all five people. An algorithm for finding a feasible matching, if any exists, will be presented in Chapter 4. Such matching graphs in which all the edges go horizontally between two sets of vertices are called bipartite. Bipartite graphs are discussed further in Section 1.3. ■ 9. Recall from Example 1 in Section 1.1 that a graph is bipartite if the vertices can be divided into two sets; for convenience call them blue vertices and red vertices, such that every edge connects a blue and a red vertex. (a) Show that if a connected bipartite graph has a Hamilton circuit, then the numbers of red and blue vertices must be equal. Further, show that if a bipartite graph has an odd number of vertices, then it has no Hamilton circuit. (b) Show that if a connected bipartite graph has a Hamilton path, then the num- bers of reds and blues can differ by at most one. Example 1: Matching Suppose that we have five people A, B, C, D, E and five jobs a, b, c, d, e, and that various people are qualified for various jobs. The problem is to find a feasible one- to-one matching of people to jobs, or to show that no such matching can exist. We A B с De W E a b d 1.1 Graph Models 5 Figure 1.2 can represent this situation by a graph with vertices for each person and for each job, with edges joining people with jobs for which they are qualified. Does there exist a feasible matching of people to jobs for the graph in Figure 1.2? The answer is no. The reason can be found by considering people A, B, and D. These three people as a set are collectively qualified for only two jobs, c and d. Hence there is no feasible matching possible for these three people, much less all five people. An algorithm for finding a feasible matching, if any exists, will be presented in Chapter 4. Such matching graphs in which all the edges go horizontally between two sets of vertices are called bipartite. Bipartite graphs are discussed further in Section 1.3. ■