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.
Let G(V,E) be a connected graph with n vertices and m edges, and positive edge costs that you may assume are all distinct. Let T=(V,E') be a spanning tree of G. We define the bottleneck edge of T to be the edge of T with greatest cost. A spanning tree T of G is a minimum bottleneck spanning tree if there is no spanning tree T/ of G with a cheaper bottleneck edge. Which of the following statement true?
S1: Every minimum bottleneck spanning tree of G a minimum spanning tree. S2: Every minimum spanning tree of G is a minimum bottleneck spanning tree of G.
Suppose we have computed a minimum spanning tree (MST) of a graph and its weight. If we make a new graph by doubling the weight of every edge in the original graph,
S1: we still need \Omega (E) time to compute the cost of the MST of the new graph. S2: MST of original graph and new graph is unchanged.
Consider sorting the edges by weight. Doubling the weight does not change the sorted order. But this means that Kruskal's and Prim's algorithm will do the same thing, so the MST is unchanged. Therefore the weight of the new tree is simply twice the weight of the old tree and can be computed in constant time if the original MST and weight are known.
Consider the following Statements for a weighted connected undirected graph.
S1: If we use a max-queue instead of a min-queue in Kruskal's MST algorithm, it will return the spanning tree of maximum total cost (instead of returning
the spanning tree of minimum total cost). S2 : If we negating all the edge weights and running Kruskal's algorithm will return the spanning tree of maximum total cost (instead of returning
the spanning tree of minimum total cost).
By using the max-queue, edges are inserted in MST in decreasing order of their weight. This will results in maximum spanning tree. Hence, S1 is true. If we negating all the edge weights, then edge with higher weight (Ex. 10 becomes -10) become less weight and reverse for smaller weight edge (Ex. 1 becomes -1). Now, is we find MST based on this modification, we get maximum spanning tree. Hence, S2 is true.