MST

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 on a tree has only one parent node.

(e) Each node on a tree has exactly two child nodes.

Page 2

4. (5 points) Decide True or False for the following statements. If True, justify answer. If False, demonstrate by examples.

(a) For an undirected graph G = (V,E), there may be more than one minimum span- ning tree (MST), but the total weights of these MSTs are the same.

(b) For an undirected graph G = (V,E), suppose an edge e is the edge with the greatest weight/cost among all the edges of the graph. Then no minimum spanning tree contains e.

(c) On the other hand, suppose an edge e is the edge with the least weight/cost among all the edges of the graph. Then every minimum spanning tree contains e.

Page 3