Discrete Quiz Ch.2

Name:______Date:______

Discrete Quiz Ch.2

1. / Which of the following describes a Hamiltonian circuit for the graph below?

A) / ABCDEFJIHG
B) / ABCDEAFJDIHBGFEJICHGA
C) / ABCDEAGHIJFA
D) / AEDCBGHIJFA
Ans: / D
2. / Which of the following describes a Hamiltonian circuit for the graph below?

A) / ABCDEFGA
B) / ACBAEGFDEA
C) / ACBFGDEA
D) / ABCDGEF
Ans: / C
3. / On the graph below, which routing is produced by using the nearest-neighbor algorithm to solve the traveling salesman problem?

A) / ABCDA
B) / ABDCA
C) / ACBDA
D) / ABCD
Ans: / B
4. / For the graph below, what is the cost of the Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at A?

A) / 60
B) / 54
C) / 62
D) / 66
Ans: / D
5. / Which path listed forms a Hamiltonian circuit on the graph below?

A) / ADCBFGHEA
B) / ABCDHGFE
C) / ABCDHGFEA
D) / ABCDHGFEHDA
Ans: / C
6. / On a map there are roads from town A of length 10, 26, 12, and 50 miles. Using the nearest-neighbor algorithm for finding a Hamiltonian circuit starting at town A, which road would be traveled first?
A) / road of length 10
B) / road of length 26
C) / road of length 12
D) / road of length 50
Ans: / A
7. / For the traveling salesman problem (Hamiltonian circuit) applied to six cities, how many tours are possible?
A) / 60
B) / 120
C) / 360
D) / 720
Ans: / B
8. / For the traveling salesman problem (Hamiltonian circuit) applied to five cities, how many unique tours are possible?
A) / 120
B) / 60
C) / 24
D) / 12
Ans: / D
9. / For the traveling salesman problem applied to seven cities, how many unique tours are possible?
A) / 360
B) / 720
C) / 2520
D) / 5040
Ans / A
10. / A connected graph G has 32 vertices. How many vertices does a spanning tree of G have?
A) / 30
B) / 31
C) / 32
D) / 33
Ans: / C
11. / On the graph below, which routing is produced by using the sorted-edges algorithm to solve the traveling salesman problem?

A) / ABCDA
B) / ABDCA
C) / ACBDA
D) / ABCD
Ans: / A
12. / For the graph below, what is the cost of the Hamiltonian circuit obtained by using the sorted-edges algorithm?

A) / 220
B) / 225
C) / 235
D) / 295
Ans: / C
13. / For the graph below, which routing is produced by using the sorted-edges algorithm to solve the traveling salesman problem?

A) / ACBEDA
B) / ABCEDA
C) / ABEDCA
D) / ADCEBA
Ans: / A
14. / Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

A) / 5
B) / 9
C) / 12
D) / 15
Ans: / B
15. / Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

A) / 23
B) / 20
C) / 16
D) / 5
Ans: / C
16. / Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

A) / 47
B) / 25
C) / 22
D) / 15
Ans: / C
17. / If the order-requirement digraph for a collection of tasks is shown below, then what is the minimum completion time for the collection of tasks?

A) / 64 minutes
B) / 43 minutes
C) / 36 minutes
D) / 28 minutes
Ans: / B
18. / What is the earliest possible completion time for a job whose order-requirement digraph is shown below?

A) / 15
B) / 22
C) / 34
D) / 19
Ans: / D
19. / The nearest-neighbor algorithm for solving the traveling salesman problem always produces the same result as the sorted-edges algorithm.
A) / True
B) / False
Ans: / B
20. / When Kruskal's algorithm is used to find a minimum-cost spanning tree on a graph, which of the following is false?
A) / Circuits are not permitted in the tree.
B) / The tree contains the edge of the graph of minimum cost.
C) / The tree is not necessarily connected.
D) / The tree may contain the edge of the highest cost.
Ans: / C
21. / A spanning tree of a graph must contain every edge of the graph.
A) / True
B) / False
Ans: / B
22. / A digraph is a graph with exactly two vertices.
A) / True
B) / False
Ans: / B
23. / The graph below shows the cost (in hundreds of dollars) of installing telephone wires between the work spaces in an office complex. Use Kruskal's algorithm for minimum-cost spanning trees to find the cost for establishing this phone network.

A) / $2100
B) / $2400
C) / $2900
D) / $6200
Ans: / B
24. / Given the two graphs shown below, which one represents a tree?

A) / I only
B) / II only
C) / Both I and II
D) / Neither I nor II
Ans: / B
25. / Kris has 3 pairs of pants of different colors, 5 shirts of different colors, and 2 pairs of shoes. How many different outfits can Kris create?
A) / 2
B) / 10
C) / 30
D) / 50
Ans: / C