Short Answer - Minimal Spanning Tree

We used the Prim minimal spanning tree algorithm for an undirected graph G= [N, E], where N is the set of nodes and E is the set of edges. Each edge is defined by a node pair (i, j). Each edge has a nonnegative length. We start at a given node and sequentially add an edge to tree at each iteration.

Say we are looking for a collection of edges that connects all the nodes with the smallest total edge length. How can you be sure that the edges selected will form a tree?

Say I give you an arbitrary tree. How could you test the tree to see if it is a minimal spanning tree?

Will you always get the same tree if you start Prim's algorithm for two different initial nodes? How will the solutions be similar?

Say you choose an initial node and find the resulting MST. You choose the same node and use some procedure to find the SPT. Say as much as you can about the difference between the two trees.

Say you have found the MST starting from some node. Under what conditions are you sure that it is the same as the SPT?

For a complete network (an edge between every pair of nodes), give an order statement about the number of steps required to find the MST.

Someone suggests the following procedure to find the MST. Sort the edges in order of increasing length. Select as the first edge in the tree the edge with the smallest length. Continue adding edges in order of length until all the nodes are connected. Will this algorithm yield the minimal spanning tree? If the algorithm doesn't work, how should it be modified?

What if there are some edges with negative length. Will Prim's algorithm still work?

You have some negative length edges in your graph. Someone suggests that you find the smallest (most negative) edge with length d (a negative number). Someone suggests you add -d to all edge lengths and solve that problem. Will the solution to the modified problem be the same as the original? Why or why not?

Give a mathematical programming model of the MST problem.

Say the edges to your problem have direction. You are looking for the tree with the shortest total arc length such that there is a directed path from the root node to every other node. Can you adapt Prim's algorithm to solve this new problem?

Return To Problems