Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged minimum-spanning-tree
2
votes
0
answers
121
Minimum Spanning Tree
Which of the following are correct for Minimum Spanning Tree from graph G with unique weights, with the weight function w: E→R (more than one possible) If we divide all weights by some non zero value MST will be unchanged (answer for both positive ... ) If we add or subtract all weights by some number MST will remain unchanged. (answer for both positive and negative values)
Which of the following are correct for Minimum Spanning Tree from graph G with unique weights, with the weight function w: E→R (more than one possible)If we divide all ...
smsubham
675
views
smsubham
asked
Dec 25, 2017
Algorithms
algorithms
minimum-spanning-tree
graph-algorithms
+
–
2
votes
1
answer
122
Minimum Spanning tree
If a simple undirected graph with positive weighted edges has 10 vertices and 30 edges, such that the cost of the Minimum Spanning tree is 59. Now, if all the edges weights are increased by 2, then the cost of the new MST is
If a simple undirected graph with positive weighted edges has 10 vertices and 30 edges, such that the cost of the Minimum Spanning tree is 59. Now, if all the edges weigh...
VIKAS TIWARI
1.7k
views
VIKAS TIWARI
asked
Dec 13, 2017
Algorithms
algorithms
minimum-spanning-tree
+
–
11
votes
3
answers
123
TIFR CSE 2018 | Part B | Question: 13
Let $n\geq 3,$ and let $G$ be a simple, connected, undirected graph with the same number $n$ of vertices and edges. Each edge of $G$ has a distinct real weight associated with it. Let $T$ be the minimum weight spanning tree of $G.$ Which of the ... edge of $C$ is not in $T.$ $T$ can be found in $O(n)$ time from the adjacency list representation of $G.$
Let $n\geq 3,$ and let $G$ be a simple, connected, undirected graph with the same number $n$ of vertices and edges. Each edge of $G$ has a distinct real weight associate...
Arjun
2.8k
views
Arjun
asked
Dec 10, 2017
Algorithms
tifr2018
graph-algorithms
minimum-spanning-tree
+
–
9
votes
2
answers
124
TIFR CSE 2018 | Part B | Question: 3
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? $1$ $2$ $4$ $6$ $8$
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?$1$$2$$4$$6$$8$
Arjun
2.6k
views
Arjun
asked
Dec 10, 2017
Algorithms
tifr2018
algorithms
minimum-spanning-tree
+
–
0
votes
2
answers
125
Minimum Spanning Tree
Multiplying all edge weights by a positive number(>1) will always change the cost of minimum spanning tree. True/False
Multiplying all edge weights by a positive number(>1) will always change the cost of minimum spanning tree.True/False
VS
3.8k
views
VS
asked
Dec 8, 2017
Algorithms
algorithms
minimum-spanning-tree
+
–
0
votes
1
answer
126
Test Series
Are MST and shortest path tree identical? T/F? with reasoning.
Are MST and shortest path tree identical?T/F? with reasoning.
targate2018
330
views
targate2018
asked
Dec 5, 2017
Algorithms
graph-theory
minimum-spanning-tree
+
–
0
votes
1
answer
127
minimum spanning tree
A complete graph G with 5 nodes has positive weight edge ,each node has distinct weight with an integer value and maximum weight is equal to the number of edges in G.What can be the maximum weight of minimum spanning tree for graph G?
A complete graph G with 5 nodes has positive weight edge ,each node has distinct weight with an integer value and maximum weight is equal to the number of edges in G.What...
set2018
620
views
set2018
asked
Nov 11, 2017
Algorithms
minimum-spanning-tree
algorithms
+
–
0
votes
1
answer
128
mst non distinct
G = (V, E ) is an undirected simple graph and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE? I. If e is the lightest edge of some cycle in G, then every MST of G includes e II. If e is the ... some cycle in G, then every MST of G excludes e (A) I only (B) II only (C) both I and II (D) neither I nor II
G = (V, E ) is an undirected simple graph and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?I. I...
Amit puri
429
views
Amit puri
asked
Nov 10, 2017
Algorithms
minimum-spanning-tree
algorithms
normal
+
–
1
votes
2
answers
129
UGC NET CSE | November 2017 | Part 2 | Question: 5
Consider the graph given below: Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are chosen is AD, AE, AG, GC, GB, BF GC, GB, BF, GA, AD, AE GC, AD, GB, GA, BF, AE AD, AG, GC, AE, GB, BF
Consider the graph given below:Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are c...
Arjun
2.4k
views
Arjun
asked
Nov 5, 2017
Algorithms
ugcnetcse-nov2017-paper2
graph-algorithms
minimum-spanning-tree
+
–
1
votes
0
answers
130
MST Kruskal
First statement is False because complexity will be O(E2). I think the second statement is true? But not sure
First statement is False because complexity will be O(E2).I think the second statement is true? But not sure
Shivam Chauhan
747
views
Shivam Chauhan
asked
Nov 2, 2017
Algorithms
algorithms
minimum-spanning-tree
time-complexity
prims-algorithm
+
–
2
votes
1
answer
131
Kruskal
Can Anyone provide all the data structure that we can used and time complexity that we get for Kruskal algorithm of finding the minimum spanning tree.
Can Anyone provide all the data structure that we can used and time complexity that we get for Kruskal algorithm of finding the minimum spanning tree.
junaid ahmad
539
views
junaid ahmad
asked
Oct 29, 2017
Algorithms
algorithms
minimum-spanning-tree
+
–
0
votes
0
answers
132
Spanning Tree
dragonball
413
views
dragonball
asked
Oct 15, 2017
Algorithms
algorithms
minimum-spanning-tree
+
–
1
votes
1
answer
133
Algorithm kruskal algorithm MST
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?
rahul sharma 5
556
views
rahul sharma 5
asked
Sep 27, 2017
Algorithms
algorithms
time-complexity
minimum-spanning-tree
+
–
1
votes
1
answer
134
[Discrete maths] Spanning trees
True/False; 1. Every tree is spanning tree.
True/False;1. Every tree is spanning tree.
rahul sharma 5
740
views
rahul sharma 5
asked
Sep 16, 2017
Graph Theory
algorithms
spanning-tree
minimum-spanning-tree
+
–
0
votes
1
answer
135
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 of edges that can change in MST of new graph w.r.t to old MST? a) 1 b) n c) Number of incident edges on new vertex n-i d) none of these
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...
AsiaPacific
692
views
AsiaPacific
asked
Sep 10, 2017
Algorithms
minimum-spanning-tree
algorithms
+
–
3
votes
0
answers
136
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 giving a counter example. I'm more interested in the converse. Please explain in detail.
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 ...
Warlock lord
824
views
Warlock lord
asked
Sep 9, 2017
Algorithms
algorithms
minimum-spanning-tree
+
–
1
votes
1
answer
137
test series( how to solve these type of problems )
vipul verma
482
views
vipul verma
asked
Aug 25, 2017
Algorithms
minimum-spanning-tree
graph-algorithms
numerical-answers
made-easy-test-series
+
–
6
votes
1
answer
138
#MST #GREEDY ALGO
Consider the following statements I. 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 to v in the graph G II.Suppose that average edge weight for a graph G is Aavg. Then ... number of vertices in graph G. which of the above statements are true ? A)Only I B)Only II C)both I and II D)None of these
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 ...
junaid ahmad
1.4k
views
junaid ahmad
asked
Jun 19, 2017
Algorithms
algorithms
minimum-spanning-tree
+
–
0
votes
1
answer
139
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 that then how to solve it .
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...
vaishali bhatia
470
views
vaishali bhatia
asked
May 23, 2017
Algorithms
algorithms
minimum-spanning-tree
+
–
1
votes
1
answer
140
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. 13 B. 14 C. 20 D. 21
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
sh!va
1.6k
views
sh!va
asked
Feb 2, 2017
Algorithms
minimum-spanning-tree
algorithms
+
–
2
votes
0
answers
141
Minimum Spanning Tree
Show the different minimum spanning Trees Possible in each of the following Algorithms Prims Algorithm Kruskal
Show the different minimum spanning Trees Possible in each of the following AlgorithmsPrims AlgorithmKruskal
Dulqar
456
views
Dulqar
asked
Jan 26, 2017
Algorithms
minimum-spanning-tree
algorithms
graph-algorithms
+
–
1
votes
2
answers
142
MadeEasy CBT 2017: Algorithms - Graph Algorithms
vaishali jhalani
2.0k
views
vaishali jhalani
asked
Jan 24, 2017
Algorithms
algorithms
minimum-spanning-tree
numerical-answers
made-easy-test-series
+
–
1
votes
1
answer
143
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?
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?
thor
424
views
thor
asked
Jan 24, 2017
Algorithms
minimum-spanning-tree
descriptive
+
–
1
votes
2
answers
144
Minimum Spanning Tree ( TestBook Test Series 2)
biranchi
663
views
biranchi
asked
Jan 23, 2017
DS
minimum-spanning-tree
graph-algorithms
+
–
1
votes
2
answers
145
number of spanning trees
Find the no. of minimum cost spanning tree using Kruskal’s or Primus algorithm i am getting "4" but the answer is given "5" ...verify please
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
Prateek kumar
1.9k
views
Prateek kumar
asked
Jan 19, 2017
Algorithms
minimum-spanning-tree
numerical-answers
+
–
0
votes
1
answer
146
Ace Test Series: Algorithms - Minimum Spanning Trees
jatinmittal199510
371
views
jatinmittal199510
asked
Jan 17, 2017
Algorithms
ace-test-series
algorithms
minimum-spanning-tree
+
–
9
votes
1
answer
147
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 can be maximum weight of minimum spanning tree for graph G?
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...
firki lama
3.5k
views
firki lama
asked
Jan 16, 2017
Algorithms
algorithms
minimum-spanning-tree
+
–
4
votes
2
answers
148
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 using array data structure ? a) O(|E|+|V log V|) b) O(|V| |log V|) c) O(|V2|) d) O(|V| |log2V|)
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...
srestha
499
views
srestha
asked
Jan 16, 2017
Algorithms
minimum-spanning-tree
algorithms
+
–
0
votes
3
answers
149
Virtual Gate Test Series: Algorithms - Minimum Spanning Tree
I think all options are wrong
I think all options are wrong
Purple
1.1k
views
Purple
asked
Jan 11, 2017
Algorithms
algorithms
spanning-tree
minimum-spanning-tree
prims-algorithm
virtual-gate-test-series
+
–
1
votes
7
answers
150
MadeEasy Subject Test: Algorithms - Minimum Spanning Trees
Kashyap Avinash
3.1k
views
Kashyap Avinash
asked
Jan 5, 2017
Algorithms
made-easy-test-series
algorithms
minimum-spanning-tree
numerical-answers
+
–
Page:
« prev
1
2
3
4
5
6
7
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register