Is the minimum spanning tree of a graph unique?
Provide an example to prove your answer.
A minimum spanning tree has already been computed for a
graph. Suppose that a new node is added (along with
appropriate costs).
How long will it take to re-compute the minimum spanning
tree?
Let T be a MST of a graph G and let L be the sorted list
of the edge weights of T.
Show that for any other MST T' of G, the list L is also the
sorted list of edge weights of T'.
You are given a directed graph, G = (V,E).
Each edge (u,v) in G has a value
r(u,v)
associated with it.
For all r(u,v),
0 <= r(u,v) <= 1.
r(u,v) can be interpreted as the probability
that a channel from u to v will
not fail, ie it's a measure of the reliability of the
channel.
Devise an efficient algorithm to find the most reliable path
between two given vertices.
Suppose that all the edge weights in a graph are integers
between 1 and | E |.
Does this improve the time to find the MST?
Does this improve the running time of Dijkstra's algorithm?
Explain how to modify Dijkstra's algorithm so that if there
is more than one minimum path from u to v,
the path with the fewest number of edges is chosen.
, 1998