Chapter Test
For the following Exercises, use the figure shown.
![Five graphs are titled graph S, graph T, graph U, graph V, and graph W. Graph S has five vertices: a, b, c, d, and e. Edges connect a b, a c, b c, c d, c e, and d e. Graph T has four vertices: a, b, d, and e. Edges connect a b, a e, b d, and d e. Graph U has 6 vertices: a, b, f, c, d, and e. Edges connect a b, a f, f d, b c, c d, d e, c e, and a c. Graph V has four vertices: a, b, d, and e.Edges connect a b, a d, a e, b d, and d e. Graph W has four vertices: a, b, d, and e. Edges connect a b, a d, and d e.]()
1
.
Name the edges in Graph T.
2
.
Identify the graph(s) with six edges.
For the following exercises, use the figure shown.
![Four graphs are titled graph A, graph B, graph C, and graph D. Graph A shows edges connecting the vertices: v q, v p, v u, v t, v s and v r. Graph B shows edges connecting the vertices: p q, q s, s t, t p, v u, and v r. Graph C shows edges connecting the vertices: p q, p u, u t, u v, t s, q s, and p t. Graph D shows edges connecting the vertices: v p, v q, v u, v t, v r, v s, p q, u t, and r s.]()
3
.
Identify any of the graphs that is a subgraph of Graph D.
4
.
Identify any graphs with no cyclic subgraphs of any size.
5
.
Consider Graph 4 and Graph 6 in the given figure. Determine if one graph is a subgraph of the other. If so, give a correspondence between vertices that demonstrates this relationship. If not, identify conflicting characteristics.
![Four graphs. Graph 3 has two overlapping quadrilaterals. The vertices of the first quadrilateral are 1, 2, 3, and 4. The vertices of the second quadrilateral are 5, 6, 7, and 8. An edge connects 2 to 6. Graph 4 has two overlapping quadrilaterals. The vertices of the first quadrilateral are 9, 10, 13, and 14. The vertices of the second quadrilateral are 15, 11, 17, and 16. A vertex, 12 is at the intersection of 15 and 11 and 13 and 10. Graph 5 has two overlapping quadrilaterals. The vertices of the first quadrilateral are 18, 19, 20, and 21. The vertices of the second quadrilateral are 22, 23, 24, and 25. Graph 6 has two overlapping quadrilaterals. The vertices of the first quadrilateral are 28, 32, 33, and 34. The vertices of the second quadrilateral are 27, 29, 30, and 31 A vertex, 26 is at the intersection of 28 and 32 and 27 and 31.]()
6
.
For the following exercise, use Graph A in the given figure. Consider each sequence of vertices. Determine if it is only a walk, both a walk and a path, both a walk and a trail, all three, or none of these.
![Two graphs are labeled graph A and graph K. Graph A has five vertices: b, c, d, e, and f. Edges connect b c, c f, b d, b e, d e, and e f. Graph K has five vertices: m, n, o, p, and q. Edges connect m n, n o, n q, q o, o p, n p, and m p.]()
d → e → b → c → f
For the following exercise, use the graphs and multigraphs in the given figure.
![Five graphs. Graph 11 has 8 vertices. Edges connect r s, s v, v u u r, t x, t w, and x w. Graph 12 has 7 vertices. Edges connect ef, f g, g e, g d, e d, e a, d a, d c, g c, c a, c b, and a b. Graph 13 has 5 vertices. Edges connect n o, n q, o m, o p, m p, m q, and q p. Multigraph 14 has 5 vertices. The edges are labeled from A to H. Multigraph 15 has 5 vertices. The edges are labeled from K to U.]()
8
.
Identify any graphs and/or multigraphs that are not Eulerian. If there are none, state so.
9
.
List the set of vertices for each component in Graph 11.
10
.
Find an Euler circuit beginning and ending at vertex b in Graph 12 if one exists.
11
.
Use Fleury’s algorithm to construct an Euler trail for the given graph beginning at vertex f of your choice.
![A graph has 7 vertices. The vertices are labeled a, b, c, d, e, f, and g. Edges connect ab, a d, d f, d e, f c, f g, c g, and e b.]()
12
.
Use the graphs shown to determine whether the sequence of vertices d → b → c → f → e → d is a Hamilton cycle, an Euler circuit, both, or neither.
![Two graphs are labeled graph A and graph K. Graph A has five vertices: b, c, d, e, and f. Edges connect b c, c f, b d, b e, d e, and e f. Graph K has five vertices: m, n, o, p, and q. Edges connect m n, n o, n q, q o, o p, n p, and m p.]()
14
.
Use the figure shown to find the weight of the given Hamilton cycle:
t → w → x → u → y → v → s → r → q → t
![Graph Z has nine vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows. 1, q to t. 2, s to v. 3, r to s. 4, q to u. 5, u to y. 6, r to v. 7, r to u. 8, v to y. 9, w to x. 10, x to y. 1, u to x. 12, t to w. 13, q to r. 14, t to u. 15, u to v.]()
t → w → x → u → y → v → s → r → q → t
For the following exercises, use this information: For the Halloween celebration at an elementary school, the students from Classroom I will visit every classroom once and return to their own classroom. The floor plan of the school is given.
![A floor plan of an elementary school. It has three blocks. The first block has front office A. The second block has three rooms: G, H, and I. The third block has five rooms: B, C, D, E, and F. Exit is at the top-right.]()
15
.
Draw a graph to represent the classrooms of the elementary school in which each vertex is a classroom and an edge between two vertices indicates that there is a path between the two rooms that does not pass the door to another classroom.
16
.
Use your graph to find a Hamilton circuit beginning and ending at I.
17
.
Explain what the Hamilton circuit you found represents for the students in Classroom I.
18
.
Find a Hamilton cycle of low weight for Graph 18, beginning at vertex q, and using the nearest neighborhood method. What is the weight of the cycle?
![Two graphs are labeled graph 17 and graph 18. Graph 17 has four vertices, a, b, c, and d. The edges are labeled as follows: a to b, 13.3; b to c, 2.0; c to d, 8.7; d to a, 9.3; a to c, 1.5; b to d, 5.2. Graph 18 has five vertices, m, q, n, p, and o. The edges are labeled as follows: m to n, 250; m to q, 100; m to p, 110; m to 0, 300; q o n, 90; q to o, 210; n to p, 75; q to p, 50; p to o, 425; n to o, 225.]()
19
.
Use Kruskal’s Algorithm to find a minimum spanning tree for the below graph. Graph the tree and give its weight.
![A graph has five vertices. The vertices are A, C, D, G, and F. The edges are labeled as follows: C to A, 130; C to D, 35; C to G, 125; C to F, 20; A to D, 45; A to F, 70; D to G, 40; A to G, 100; G to F, 15; D to F, 30.]()