## 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?