Contemporary Mathematics

# Chapter Test

### Chapter Test

For the following Exercises, use the figure shown.
1 .
Name the edges in Graph T.
2 .
Identify the graph(s) with six edges.
For the following exercises, use the figure shown.
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.
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.
debcf
7 .
For the following exercise, use Graphs A and K in Figure 12.369. Determine the chromatic number of Graph K. Give a coloring that supports your conclusion.
For the following exercise, use the graphs and multigraphs in the given figure.
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.
12 .
Use the graphs shown to determine whether the sequence of vertices dbcfed is a Hamilton cycle, an Euler circuit, both, or neither.
13 .
Calculate the number of distinct Hamilton cycles in a complete graph with 15 vertices.
14 .
Use the figure shown to find the weight of the given Hamilton cycle:
twxuyvsrqt
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.
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?
19 .
Use Kruskal’s Algorithm to find a minimum spanning tree for the below graph. Graph the tree and give its weight.
Order a print copy

As an Amazon Associate we earn from qualifying purchases.