Quiz #10 -- Take Home to be turned in on Final Exam Day						Math 116
Name___________________________________
 
MULTIPLE CHOICE.  Choose the one alternative that best completes the statement or answers the question. 
Solve the problem. 
1) 

Which of the following four graphs is a tree?

1) 

_______ 
A) 

Graph 1 and Graph 4 
B) 

Graph 2 and Graph 4 
C) 

Graph 1 and Graph 3 
D) 

Graph 2 and Graph 3 
E) 

None of the above 
 
2) 

The number of vertices in a tree with 57 edges is 

2) 

_______ 
A) 

. 
B) 

56. 
C) 

57. 
D) 

58. 
E) 

None of the above 
 
3) 

How many spanning trees does the following graph have?

3) 

_______ 
A) 

5 
B) 

3 
C) 

4 
D) 

8 
E) 

None of the above 
 
The question(s) that follow refer to the problem of finding the minimum spanning tree for the weighted graph shown below.
 
4) 

The total weight of the minimum spanning tree is 

4) 

_______ 
A) 

125. 
B) 

24. 
C) 

26. 
D) 

68. 
E) 

None of the above 
 
Use the mileage chart shown below to find the minimum spanning tree for the 5 cities of Boston, Buffalo, Chicago, Columbus, and Louisville.
 
5) 

Using Kruskal's algorithm which edge is chosen third? 

5) 

_______ 
A) 

Buffalo - Columbus. 
B) 

Boston - Buffalo. 
C) 

Columbus - Louisville. 
D) 

Boston - Chicago. 
E) 

None of the above 
 
Solve the problem. 
6) 

Which of the following statements is true about Kruskal's algorithm. 

6) 

_______ 
A) 

It is an inefficient algorithm, but it always gives the minimum spanning tree. 
B) 

It is an efficient algorithm, but it doesn't always give the minimum spanning tree. 
C) 

It is an efficient algorithm, and it always gives the minimum spanning tree. 
D) 

It is an inefficient algorithm, and it never gives the minimum spanning tree. 
E) 

None of the above 
 
7) 

Every Steiner point has a degree of 

7) 

_______ 
A) 

2. 

B) 

4. 

C) 

1. 

D) 

3. 

E) 

0. 
 
New telephone lines must be installed to connect 8 cities (A, B, C, D, E, F, G, and H). Due to government regulations, the only possible connections that are allowed are shown by the edges on the graph below. The numbers on the edges indicate the cost (in millions of dollars) of each possible connection. The telephone company wishes to connect the cities in the cheapest possible way.
 
8) 

The number of bridges in the optimal solution to this problem is 

8) 

_______ 
A) 

9. 
B) 

7. 
C) 

0. 
D) 

8. 
E) 

None of the above 
 
Solve the problem. 
9) 

The shortest network connecting the points A, B, and C shown below has

9) 

_______ 
A) 

a Steiner junction point inside the triangle ABC. 
B) 

no junction point. 
C) 

a Steiner junction point outside the triangle ABC. 
D) 

a junction point at A. 
E) 

None of the above 
 
10) 

One of the four points below - W, X, Y, or Z - is a Steiner point of triangle ABC.  Which one?

10) 

______ 
A) 

W 
B) 

X 
C) 

Z 
D) 

Y 
E) 

All of the above 

1) 

C 
2) 

D 
3) 

B 
4) 

B 
5) 

A 
6) 

C 
7) 

D 
8) 

B 
9) 

A 
10) 

D