Register

Recent questions tagged minimum-spanning-tree

2 2 votes
2 2 answers
2.1k
2.1k views
Graph Theory
Consider a 'reversed Kruskal' Algorithm for computing a MST. Initialize T to be the set of all edges in the graph. Now consider edges from largest to smallest cost. For e...
User Avatar
0 0 votes
1 1 answer
1.1k
1.1k views
Minimum Spanning Trees
Suppose, the MST of a graph of n vertices has already been constructed. Now, if one new vertex is added to the graph along with 'i' incident edges. What is the max number...
User Avatar
3 3 votes
0 0 answers
1.1k
1.1k views
cormen
Show that a graph has a unique minimum spanning tree if, for every cut of the graphs, there is a unique line edge crossing the cut. Show that the converse is not true by ...
User Avatar
1 1 vote
1 1 answer
820
820 views
test series( how to solve these type of problems )
User Avatar
4 4 votes
1 1 answer
1.8k
1.8k views
#MST #GREEDY ALGO
Consider the following statementsI. Let T be a minimum spanning tree of a graph G.Then for any two vertices u and v the path from u to v in T is the shortest path from u ...
User Avatar
2 2 votes
1 answers 1 answer
851
851 views
Test by Bikram | Algorithms | Test 2 | Question: 20
Consider the following Graph G: The number of minimum cost spanning trees using Kruskal's Algorithm is _________ .
User Avatar
1 1 vote
1 answers 1 answer
534
534 views
Test by Bikram | Algorithms | Test 2 | Question: 11
Let the node P be the starting vertex for Prim's Algorithm as given in the diagram below:In order to construct the Minimum Spanning Tree, which of the following options r...
User Avatar
0 0 votes
1 1 answer
883
883 views
Minimum number of spanning tree
For finding minimum number of spanning tree using kirchoff rule we construct adjacency matrix and find cofactors.so my question is what if we have 6*6 matrix or more than...
User Avatar
1 1 vote
3 3 answers
7.3k
7.3k views
No of spanning Trees
Let $K_n$ denote the complete undirected graph with $n$ vertices where n is an even number. Find the maximum number of spanning trees of $K_n$ that can be formed in such ...
User Avatar
0 0 votes
1 1 answer
662
662 views
testbook
User Avatar
1 1 vote
1 answers 1 answer
2.0k
2.0k views
Minimum spanning tree
In given graph G if only AC and BC belong to its minimum spanning tree, then what can be the minimum sum of weights of all edges in the graph G?A. 13B. 14C. 20D. 21
User Avatar
2 2 votes
0 0 answers
678
678 views
Minimum Spanning Tree
Show the different minimum spanning Trees Possible in each of the following AlgorithmsPrims AlgorithmKruskal
User Avatar
1 1 vote
2 2 answers
2.6k
2.6k views
MadeEasy CBT 2017: Algorithms - Graph Algorithms
User Avatar
1 1 vote
1 1 answer
861
861 views
Graph MST
For a simple, undirected, weighted graph each edge havind distinct weight, How is it possible that there can be more than $1$ second best minimum spanning tree?
User Avatar
1 1 vote
2 2 answers
1.0k
1.0k views
Minimum Spanning Tree ( TestBook Test Series 2)
User Avatar
1 1 vote
2 answers 2 answers
3.2k
3.2k views
number of spanning trees
Find the no. of minimum cost spanning tree using Kruskal’s or Primus algorithmi am getting "4" but the answer is given "5" ...verify please
User Avatar
0 0 votes
1 1 answer
623
623 views
Ace Test Series: Algorithms - Minimum Spanning Trees
User Avatar
9 9 votes
1 answers 1 answer
5.4k
5.4k views
maximum weight of minimum spanning tree??
A complete graph G with 5 nodes has positive weight edges,each edge has a distinct weight with an integer value and maximum weight is equal to number of edges in G.What c...
User Avatar
4 4 votes
2 2 answers
881
881 views
MST..
Let G(V, E) be an undirected graph with positive edge weights. What is the worst case time complexity to find minimum spanning tree using Kruskal algorithm is implemented...
User Avatar
0 0 votes
3 3 answers
2.3k
2.3k views
Virtual Gate Test Series: Algorithms - Minimum Spanning Tree
I think all options are wrong
User Avatar
2 2 votes
7 answers 7 answers
7.6k
7.6k views
MadeEasy Subject Test: Algorithms - Minimum Spanning Trees
User Avatar
0 0 votes
1 1 answer
751
751 views
Algo-MST
how many numbers of MST possible for n vertex:1. all the weight edges are distinct2. all the weight edges are different
User Avatar
1 1 vote
1 answers 1 answer
1.3k
1.3k views
Algo-MST
Which one of the following is true?1) For any graph G Kruskal and Prims both give same MST.2)The running time of Prims algo can be improved if we use Fibonacci Heap inste...
User Avatar
1 1 vote
0 0 answers
711
711 views
MadeEasy Test Series: Algorithms - Minimum Spanning Trees
adding a constant to graph edges doesnt change the edges that belong to minimum spanning tree of the graph ryt?
User Avatar
0 0 votes
2 answers 2 answers
2.7k
2.7k views
cormen chapter 23 third edition.
Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of one of the edges in T. Show that T is still a minimum spanning tree for G. More form...
User Avatar
4 4 votes
1 answers 1 answer
2.6k
2.6k views
Spanning Trees
Consider the following adjacency matrix representation of connected graph then find the number of spanning trees are possible for the given graph$\begin{bmatrix} 0&1&1&1&...
User Avatar
2 2 votes
1 answers 1 answer
780
780 views
minimum spanning tree
User Avatar
1 1 vote
1 1 answer
502
502 views
Discrete maths
https://gateoverflow.in/?qa=blob&qa_blobid=15165260876214054240
User Avatar
0 0 votes
0 0 answers
594
594 views
Kerala PSC AP Exam
Let G be a weighted undirected graph and e be an edge with mazimum weight in G. suppose there is a minimum weight spanning tree in G containing edge e. which of the follo...
User Avatar
2 2 votes
3 3 answers
2.5k
2.5k views
#algorithm
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
User Avatar
Page: