Hon Discrete CHAPTER 7 Practice Multiple Choice: SOLUTIONS
1) Which of the four graphs pictured below are trees?
Graph #1 / Graph #2 / Graph #3 / Graph #4A) Graph 2B) Graph 2 and 4C) Graph 2 and 3
D) Graph 2, 3, and 4E) None of the Above
2) Which of the four graphs pictured below are not trees?
Graph #1 / Graph #2 / Graph #3 / Graph #4A) Graph 3B) Graph 2 and 4C) Graph 2 and 3
D) Graph 1 and 3E) None of the Above
3) The number of vertices in a tree with 12 edges is
A) 10B) 11C) 12D) 13E) None of the above
4) Assume graph G has no loops or multiple edges. Which of the following graphs are definitely trees?
A) G has 9 vertices and 8 bridges.B) G has 11 vertices and 9 edges
C) G has 7 vertices and no circuits.D) All of the above graphs are trees.
E) None of the above graphs are trees.
5) The number of edges in a tree with 32 vertices is
A) 30B) 31C) 32D) 33E) None of the above
6) Suppose a graph has 15 vertices and 14 edges. Then
A) Graph must be a tree.
B) Graph is either a tree or it is not connected.
C) G cannot have any circuits.
D) G cannot have more than one path joining any two vertices.
E) None of the above.
7) How many spanning trees does the graph in Figure #1 have?
A) 3
B) 4
C) 5
D) 8
E) None
8) How many spanning trees does the graph in Figure #2 have?
A) 10
B) 15
C) 23
D) 24
E) None
9) How many spanning trees does the graph in Figure #3 have?
A) 11
B) 55
C) 59
D) 60
E) None
10) How many spanning trees does the graph in Figure #4 have?
A) 19
B) 20
C) 392
D) 419
E) 420
For #11 and 12, use Figure #5.
______11) Using Kruskal’s algorithm, which edge should you choose second?
A) AEB) AB
C) BDD) DE
E) None of the above
______12) Using Kruskal’s algorithm, which edge should you choose fourth?
A) ABB) BC
C) BDD) DE
E) None of the above
HONORS DISCRETE CHAPTER 7 REVIEW - SOLUTIONS
1)Identify if each graph is a tree or is not a tree.
- If possible, find a spanning tree in the network.
- Calculate the redundancy of each graph
2)How many possible spanning trees exist in the network?
4) Determine if the follow descriptions of a graph are (1) ALWAYS A TREE, (2) NEVER A TREE, or (3) SOMETIMES A TREE.
#1: 9 vertices and 8 edges.
SOMETIMES
#2: 5 bridges and 6 vertices.
ALWAYS
#3: 18 edges and 17 vertices.
NEVER
#4:7 vertices and no circuits
SOMETIMES
#5:14 vertices and 12 bridges.
NEVER
#6: Only one path exists between any two vertices in the graph.
ALWAYS
#7: Connected graph with Redundancy = 0
ALWAYS
#8: 5 edges and 5 vertices.
NEVER
5) Find the minimum spanning tree using Kruskal’s algorithm and provide the overall weight of the MST.