CSC3360 Analysis of Algorithms Fall 2022

HW â€“ Minimum Spanning Trees (MST)

Objectives

â€¢ Be familiar with relationship and distinction between trees and graphs.

â€¢ Be familiar with minimum spanning tree algorithms.

â€¢ Be able to solve optimization problems using minimum spanning tree algorithms

Key Ideas

â€¢ Trees

â€¢ Minimum spanning trees (MST)

â€¢ Kruskalâ€™s algorithm

â€¢ Primâ€™s algorithm

â€¢ Minimax problem.

Homework Problems

Reference: Lecture notes and Chapter 23

1. (15 points)

5 3 1

4 5 2

4 6 6

9 7 2 2

1 3 7 1

ï¿½ï¿½

ï¿½ï¿½

3 ï¿½ï¿½

ï¿½ï¿½

6 ï¿½ï¿½

ï¿½ï¿½

9 ï¿½ï¿½

ï¿½ï¿½

12

ï¿½ï¿½

ï¿½ï¿½

2 ï¿½ï¿½

ï¿½ï¿½

5 ï¿½ï¿½

ï¿½ï¿½

8 ï¿½ï¿½

ï¿½ï¿½

11

ï¿½ï¿½

ï¿½ï¿½

1 ï¿½ï¿½

ï¿½ï¿½

4 ï¿½ï¿½

ï¿½ï¿½

7 ï¿½ï¿½

ï¿½ï¿½

10

The graph above represents a mountain area where several small towns are located,

vertices represent towns, edges represent roads connecting the towns and the number

on each edge represents the highest elevation (in thousands of feet) encountered as the

edge (road) is traveled. We wish to find a path from vertex 1 to vertex 12 on this graph

with the property that the highest elevation encountered along the path is as small as

possible. We seek such a path from vertex 1 to vertex 12 because we (travelers) wish to

avoid high altitude.

(a) Find a minimum spanning tree for this graph. Note: Upon completion, take the

tree out of the graph and draw it separately.

(b) What is the maximum (highest) altitude encountered along the path from 1 to 12

in the tree of part (a)?

(c) Is there any smaller maximum altitude among all other possible paths from 1 to 12

than the one found in part (b)? If so, what is it?

2. (15 points) Suppose you are asked to network six computers on campus so any two

computers can communicate each other directly or through other computers. The cost

of a connection between two computers is proportional to the distance between them.

Assume that the unit cost is $10 per yard. Below is the distance between pairs of

computers on campus (in tens of yards).

Computer 1 2 3 4 5 6

1 0 5 5 3 8 6

2 5 0 6 5 4 5

3 5 6 0 5 5 3

4 3 5 5 0 6 6

5 8 4 5 6 0 4

6 6 5 3 6 4 0

(a) Formulate the problem as a MST graph problem.

(b) How would the six computers be connected so that the entire network is the cheap-

est.

(c) What is the total cost of the cheapest network?

3. (5 points) Decide True or False for the following statements. Justify your answers.

(a) A connected, undirected graph with no cycles is a tree.

(b) Any connected, undirected graph with n nodes and nâˆ’ 1 edges must be a tree.

(c) An undirected graph is a tree if and only if there is a unique path between any pair

of nodes.

(d) Each node except the root