Minimum-Cost Spanning Trees Quiz

Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

• A) 20

• B) 14

• C) 19

• D) 16

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) $2200

• C) $2400

• D) $2900

A connected graph G has 31 vertices. How many edges does a spanning tree of G have?

• A) 30

• B) 31

• C) 32

• D) 33

In which of the diagrams below do the wiggled edges represent spanning trees?

• I only

• II only

• Both I and II

• Neither I nor II

Suppose a maintenance worker needs to empty garbage dumpsters from five locations on the grounds of a park in the most efficient way possible. The technique most likely to be useful in solving this problem is:

• finding an Euler circuit on a graph.

• applying the nearest-neighbor algorithm for the traveling salesman problem.

• applying Kruskal’s algorithm for finding a minimum-cost spanning tree for a graph.

• None of these techniques is likely to apply.

Use modified Kruskal’s algorithm for maximum-cost spanning trees on the graph below. The cost of the tree found is:

• 22

• 32

• 40

• 49