Chat with us, powered by LiveChat 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 | paledu.org
  

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