Dark Mode

Recent questions tagged minimum-spanning-tree

0 votes

2 answers

61

Gateforum Test Series: Algorithms - Minimum Spanning Trees

Prince Sindhiya asked in Algorithms Jan 20, 2019

by Prince Sindhiya

648 views

0 votes

0 answers

62

Ace Test Series: Algorithms - Minimum Spanning Tree

jhaanuj2108 asked in Algorithms Jan 4, 2019

443 views

0 votes

2 answers

63

UGC NET CSE | December 2018 | Part 2 | Question: 12
Consider the graph shown below: Use Kruskal’s algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is $17$ $14$ $16$ $13$

Arjun asked in Unknown Category Jan 2, 2019

by Arjun

4.3k views

0 votes

0 answers

64

DOUBT ON MINIMAL SPANNING TREE
II. if an edge (u,v) is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph. III. If (u,v) is a light edge connecting CC(connected component) to some other component in the forest of graph ... spanning tree. didn't understand the part light edge crossing some cut of the graph can someone explain me with the diagram ??

Magma asked in Algorithms Dec 28, 2018

by Magma

520 views

1 vote

1 answer

65

Gateforum Test Series: Algorithms - Minimum Spanning Trees

Gupta731 asked in Algorithms Dec 23, 2018

863 views

0 votes

2 answers

66

GAte zeal mock
I got 41 as answer please verify

Prince Sindhiya asked in Graph Theory Dec 21, 2018

by Prince Sindhiya

575 views

0 votes

0 answers

67

Zeal Test Series 2019: Algorithms - Minimum Spanning Trees
How many of following are correct statements ? (i) A graph where all edge weights are distinct can have more than one shortest path between two vertices u and v (ii)adding a number w on weight of every edge of graph ... number might change the shortest path between two vertices u and v (Assume that all edge weights of graph are distinct)

Prince Sindhiya asked in Algorithms Dec 21, 2018

by Prince Sindhiya

884 views

0 votes

0 answers

68

MadeEasy Test Series: Algorithms - Minimum Spanning Trees
How to solve such type of questions ?

Avijit Shaw asked in Algorithms Dec 20, 2018

682 views

11 votes

5 answers

69

TIFR CSE 2019 | Part B | Question: 2
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? $8$ $16$ $32$ $64$ None of the above

Arjun asked in Algorithms Dec 18, 2018

by Arjun

4.6k views

0 votes

1 answer

70

MadeEasy Test Series: Algorithms - Minimum Spanning Trees

mitesh kumar asked in Algorithms Dec 17, 2018

by mitesh kumar

986 views

0 votes

1 answer

71

Made easy test series
What we do if graph is complete with 5 vertices and weight are 1,2,3,4,5,6,7,8,9 and 10. than find maximum possible weight that a minimum weight spanning tree of G have..???

Vikas123 asked in Algorithms Dec 14, 2018

1.6k views

0 votes

0 answers

72

made easy tt2
consider the following graph in which x represents the number of minimum cost spanning tree and y represents the number of 2nd minimum cost spanning tree.which of the following represents $\left | 2^{x}-2^{y} \right |$? i am getting x=27 but they have given x=9 pls ... at right side ; total ways =3*3*3 = 27 number of minimum spanning tree = 27?? isnt this correct?? pls someone help!!

Gate Fever asked in Algorithms Dec 1, 2018

754 views

0 votes

0 answers

73

HeadShot asked in Algorithms Nov 30, 2018

493 views

0 votes

0 answers

74

Algorithm-METest-MST
A Spanning tree T(V,E) has bottleneck edge, means all edges present in T with the greatest cost would be bottleneck edges. Now they have said, A spanning tree T of G is a minimum bottleneck spanning tree if no spanning tree T' existed with cheaper ... I think if in (A) it was minimum bottleneck spanning tree, then (B) would not have been possible to produce. Please guide.

Ayush Upadhyaya asked in Algorithms Nov 17, 2018

by Ayush Upadhyaya

1.1k views

0 votes

0 answers

75

Find the weight MST
Let us assume that $G$($V$, $E$) is a weighted complete graph such that weight of the edge <$V_K$,$V_L$>=2|$K$-$L$|. The weight MST of $G$ with 100 vertices is ____________________.

Naveen Kumar 3 asked in Algorithms Nov 10, 2018

by Naveen Kumar 3

659 views

0 votes

0 answers

76

Minimum spanning tree implementation in other way
Which algorithm will be implemented on the weighted graph in which the edges are uniformly distributed over the half-open interval $[0,1)$ to construct MST so that it runs in linear time? $A)$ Kruskal's algorithm $B)$ Prim's algorithm $C)$ Both $(A)$ and $(B)$ $D)$ None of these

Lakshman Bhaiya asked in Algorithms Nov 10, 2018

by Lakshman Bhaiya

517 views

0 votes

1 answer

77

Self doubt Spanning tree
How many numbers of spanning tree are possible?

Lakshman Bhaiya asked in Algorithms Nov 8, 2018

by Lakshman Bhaiya

1.1k views

2 votes

1 answer

78

Spanning Tree
How to count the number of spanning tree?

Lakshman Bhaiya asked in Algorithms Nov 8, 2018

by Lakshman Bhaiya

1.4k views

0 votes

1 answer

79

#self doubt #minimum spanning tree
T/F In a graph G=(V,E) suppose that each edge e ∊ E has an integer weight w(e) such that 1<= W(e) <=n Then there is a an o(mlogn) time algorithm to ﬁnd a minimum spanning tree in G. Also,Does this "weight w(e) such that 1<= W(e) <=n" has significance on time complexity or we consider it as some edges weights and proceed?

meghna asked in Algorithms Oct 3, 2018

by meghna

347 views

0 votes

0 answers

80

Cormen
Let $T$ be a minimum weight spanning tree of graph $G = (V, E)$, and let $V’$ be a subset of $V$ . Let $T'$ be a sub-graph of $T$ induced by $V'$ and let $G’$ be a sub-graph of $G$ induced by $V'$. Prove that If $T'$ is connected , then $T'$ is a minimum weight spanning tree of graph $G′$

sushmita asked in Algorithms Sep 27, 2018

460 views

0 votes

2 answers

81

Algorithm 19
Why 2nd statement false

Deepalitrapti asked in Algorithms Sep 12, 2018

by Deepalitrapti

977 views

0 votes

2 answers

82

GATE Minimum Spanning Trees
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?

Nidhi Budhraja asked in Mathematical Logic Aug 31, 2018

by Nidhi Budhraja

751 views

0 votes

3 answers

83

Spanning Tree
2) An undirected graph G has n nodes. Its adjacency matrix is given by an n n square matrix whose (i) diagonal elements are 0 s and (ii) non-diagonal elements are 1 s. which one of the following is TRUE? (a) Graph G has no minimum spanning tree (MST) ... n-1 (c) Graph G has multiple distinct MSTs, each of cost n-1 (d) Graph G has multiple spanning trees of different costs Expain?

pradeepchaudhary asked in Algorithms Jul 23, 2018

by pradeepchaudhary

1.1k views

1 vote

1 answer

84

Kruskal Algorithm
Complexity of Kruskal's algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are unsorted is _______ ______________________________________________________________________________ If elements are sorted we do with Union Find algo with ... is $log^{*}V$ Now from here can we derive it for unsorted edges? for ref: here

srestha asked in Algorithms Jun 30, 2018

1.6k views

–1 vote

1 answer

85

Ace Test Series: Algorithms - Minimum Spanning Trees

Na462 asked in Algorithms Jun 29, 2018

by Na462

721 views

1 vote

2 answers

86

Minimum spanning tree
What would be the maximum weight of minimum spanning tree of a complete connected graph with 6 vertex where each edge is of distinct +ve weights and max weight of edge is 15 1) 25 2) 26 3)27 4) none of these

Rohit Pandey asked in Algorithms Jun 28, 2018

by Rohit Pandey

772 views

0 votes

1 answer

87

Made easy workbook

shweta sah asked in Algorithms Jun 21, 2018

261 views

0 votes

1 answer

88

self doubt
Suppose that average edge weight for a graph G is Aavg. Then the minimum spanning tree of G will have weight at most (n-1) Aavg. Where n is number of vertices in graph G. i think think is false but in a solution mannul it is given as true please check it.

eyeamgj asked in Algorithms Jun 16, 2018

818 views

1 vote

4 answers

89

madeeasy work book
Q. State whether the following statements are FALSE. (a). if $e$ is the minimum edge weight in a connected weighted graph,it must be among the edges of at least one minimum spanning tree of the graph. (b). if $e$ is the minimum edge weight ... connected weighted graph,it must be among the edges of each one minimum spanning tree of the graph. which one is correct above two option?

abhicse asked in Algorithms May 24, 2018

2.9k views

4 votes

1 answer

90

Minimum Spanning Tree
1) Kruskal Algorithm 2) Prims Algorithm 3) Dijkstra Algorithm 4) Bellman Ford Algorithm 5) Floyd Warshall Algorithm Among these which one works for only i) Positive edge weight ii) Negative edge weight iii) Negative weight cycle

srestha asked in Algorithms Apr 30, 2018

3.1k views

Page:

« prev
1
2
3
4
5
6
7
next »

Recent questions tagged minimum-spanning-tree