Suppose we run Prim's algorithm and Kruskal's algorithm on a graph G and the two
algorithms produce minimum-cost spanning trees TP and TK, respectively. Which of the following is true?
A
TP must be identical to TK.
B
If e is a minimum cost edge in G, e belongs to both TP and TK.
C
If TP is different from TK, some pair of edges in G have the same weight.
D
If e is a maximum cost edge in G, e belongs to neither TP nor TK.
For a graph having more than one edges having same weight, different MST can be possible using kruskal's and prim's algorithm. Hence option A is false. Here more than one edges possible with minimum cost weight. So it might possible that e will not be selected in resultant MST. Hence, option B is false. It might possible that graph having maximum cost edge connect the vertice and removal of it disconnect the graph, then that edge must be part of MST. Hence, option D is false. If prim's and kruskal's algorithm results in different MST but cost of MST must be same. To satisfy this, option C must be true.
Consider the following algorithm on a graph with n vertices and m edges.
Sort the edges as [e1,e2,...,em] in decreasing order of cost.
Start with the original graph. Consider each edge ej. If this edge is part of a cycle delete it.
Which of the following is not true?
A
After processing all m edges, the resulting graph is connected
B
What remains at the end is a minimum cost spanning tree
This is reverse version of Kruskal's algorithm. Any edge that is part of a cycle can be deleted without
disconnecting the graph. In the end we get a minimum cost spanning tree with exactly n-1 edges. Hence, total edges deleted = m-(n-1)=m-n+1.
Suppose we have a graph with negative edge weights. We take the largest magnitude
negative edge weight -k and reset each edge weight w to w+k+1. Which of the following is true?
A
Kruskal's algorithm will identify the same spanning tree on the new graph as on the old
graph.
B
Minimum cost spanning trees in the original graph will not correspond to minimum cost spanning trees in the new graph.
C
Prim's algorithm will not work on the original graph but will work on the modified graph
D
There are more minimum cost spanning trees in the modified graph than in the original
graph.
The ascending order of edge weights is unchanged if each edge weight is increased by k+1, so Kruskal's
algorithm runs in exactly same way as before and produces the same tree. In general, since every
spanning tree has exactly n-1 edges, the increase in weight uniformly affects all spanning trees, so the
minimum cost spanning trees are unchanged. Prim's algorithm is not affected by negative weights.
As given that the weights are all distinct positive integers, least weight edge always becomes part of MST It might possible that graph having maximum cost edge connect the vertex and removal of it disconnect the graph, then that edge must be part of MST. second smallest weighted edge can never eliminated while removing the edges which create loops in MST. Hence, it is always part of MST. Third smallest edge might create loop with two edges with minimum cost. So, resulting MST will not select this edge.