Vertex
A is adjacent toGreat Ideas in Mathematics
Math 110 - Fall 2007
Ch. 5: Euler paths and circuits
Practice questions
More questions may be posted later
Some answers are below.
The next six questions refer to the diagram at the right.
1.
Vertex
A is adjacent to
A vertex B and vertex E only.
B vertex D only.
C every other vertex.
D vertex C and vertex D only.
E none of these above
2. The degree of vertex D is
A 4 ˝
B 3
C 4
D 5
E none of these
3. The degree of vertex E is
A 5
B 2
C 3
D 4
E none of these
4. Which of the following is not a path from vertex D to vertex A?
A D, E, C, D, A
B D, C, A
C D, C, C, A
D D, E, D, C, C, A
E all of these are paths from D to A
5. Which of the following is not a circuit in the graph?
A A, D, E, C, A
B E, D, C, C, E
C A, D, C, D, E, D, A
D C, A, D, C
E All of the above are circuits
6. Which of the following is a bridge in the graph?
A EC
B BD
C AD
D CC
E none of these
7.
Which
of these graphs has/have Euler circuit(s) ?
A Graph 3 only
B Graphs 1 and 3
C Graph 2 only
D Graph 1 only
E None of the above
8.
Which
of these graphs has an Euler path but does not have an Euler circuit ?
A Graph 3 only
B Graphs 1 and 3
C Graph 2 only
D Graph 1 only
E None of the above
The next three questions to the following situation: An undercover police officer is assigned the job of walking once a night each of the 48 blocks of a certain section of town described by the street grid shown below. The walk starts and ends at A. The officer wants to minimize the total number of blocks he has to walk each night.
9. How many vertices of odd degree are there in the graph representing this problem?
A 20
B 22
C 18
D 24
E none of these
10. An optimal eulerization of the graph representing this problem can be obtained by adding
A 9 edges
B 11 edges
C 12 edges
D 10 edges
E none of these
11. Suppose that it takes the officer 5 minutes to walk a block. In an optimal trip, the officer will cover the entire neighborhood in
A 5 hours and 10 minutes
B 5 hours
C 4 hours and 45 minutes
D 4 hours and 50 minutes
E none of these
12. A graph has an Euler circuit if
A every vertex has even degree
B it is connected and has an even number of vertices
C it is connected and has an even number of edges
D it is connected and every vertex has even degree
E none of these
13. A graph with 11 vertices has an Euler path but no Euler circuit. The graph must have
A 11 vertices of even degree
B 11 vertices of odd degree
C 2 vertices of odd degree and 9 vertices of even degree
D 2 vertices of even degree and 9 vertices of odd degree
E none of these
14. A graph has six vertices—two vertices of degree 4, two vertices of degree 3, and two vertices of degree 2. The number of edges in the graph is
A 9
B 6
C 5
D 8
E none of these
15. The basic rule in Fleury’s algorithm is
A only travel across a bridge of the untraveled part of the graph if there is no other alternative
B only travel across a bridge of the original graph if there is no other alternative.
C never travel across a bridge of the original graph.
D never travel across a bridge of the untraveled part of the graph.
E none of these
The next six questions refer to the diagram at the right.
16.
Vertex E is adjacent to
A B and D only
B B, C and D only
C C and D only
D every other vertex
E none of these
17. The degree of vertex D is
A 3
B 4
C 2
D 1
E none of these
18. The degree of vertex C is
A 1
B 2
C 3
D 4
E none of these
19. Which of the following is not a path from vertex D to vertex A
A all of these are paths
B D, C, C, B, A
C D, E, B, D, C, B, A
D D, A
E D, C, B, A
20.
Which of the following is not a circuit in the graph?
A B, D, E, B, A, D, B
B B, C, C, D, B
C B, D, E, B
D B, C, D, B
E all of the above are circuits in the graph
21. Which of the following is a bridge of the graph?
A DE
B there are no bridges in this graph
C BD
D AB
E AD
The next two questions refer to a graph (not pictured) with vertices A, B, C, D and E and edges BC, CE, AB, AC and BD
22. The degree of vertex B is
A 0
B 1
C 2
D 3
E none of these
23. Which of the following is a bridge of the graph
A BD
B AC
C BC
D AB
E none of these
The next three questions refer to the four graphs shown below:
24. Which graph has an Euler circuit?
A Graph 1
B Graph 2
C Graph 3
D Graph 4
E none of these
25. Which graph(s) are disconnected?
A Graphs 1 and 4
B Graph 3 only
C Graph 2 only
D Graphs 2 and 3
E none of these
26. Which graph has an Euler path but no Euler circuit?
A Graph 1
B Graph 2
C Graph 3
D Graph 4
E none of these
The next two questions refer to the graph below:
27. Which of the drawings has an open unicursal tracing?
A Figure 1 only
B Figures 2 and 3 only
C Figure 3 only
D Figure 2 only
E none of these
28. Which of the drawings has a closed unicursal tracing?
A Figure 1 only
B Figures 2 and 3 only
C Figure 3 only
D Figure 2 only
E none of these
29. A graph (not pictured) has seven vertices, two vertices of degree 6, four vertices of degree 5 and one vertex of degree 2. The number of edges in the graph is
A 7
B 13
C 14
D 17
E none of these
30.
In a certain city there is a river running through the middle of the
city. There are four islands and
nine bridges, as shown in the figure at the right.
The graph that represents this information has
A 9 vertices and 6 edges
B 4 vertices and 9 edges
C 6 vertices and 9 edges
D 9 vertices and 4 edges
E none of these
31. Match the name of the item to its description.
|
|
Any edge that starts and ends at the same vertex |
|
A |
adjacent edges |
|
|
Any edge that disconnects the graph when deleted |
|
B |
connected graph |
|
|
Any line joining two vertices of the graph |
|
C |
edge |
|
|
The point where two or more edges meet |
|
D |
degree |
|
|
The number of edges that meet at a given vertex |
|
E |
loop |
|
|
Two edges of a graph connected by a common vertex |
|
F |
bridge |
|
|
Two vertices joined by a single edge |
|
G |
adjacent vertices |
|
|
Any sequence of adjacent edges which appear only once |
|
H |
path |
|
|
A sequence of adjacent vertices that start and end at the same place |
|
I |
circuit |
|
|
A graph where any two vertices are joined by a path |
|
J |
vertex |
Created November 26, 2007
Some of the Answers
1 D
2 D
3 C
4 E
5 C
6 B
7 A
8 D
9 A
10 D
11 D
12 D
13 C
14 A
15 A
16 A
17 B
18 D
19 A
20 A
21 B
22 D
23 A
24 A
25 D
26 D
27 B
28 A
29 D
30 C
31 EFCJD AGHIB
End of the answers