Recent questions tagged minimum-spanning-tree / GATE Overflow for GATE CSE

2 votes

0 answers

31

Why does Kruskal's algorithm find the minimum spanning tree if it's greedy? Isn't a minimum spanning tree a global optimization problem? Isn't the point of being greedy is that there is a chance you won't find the most optimal solution? So how can Kruskal be able to find the minimum spanning tree while also being greedy?

Please can anyone tell me though Prim’s and Kruskal’s algorithms are greedy algorithms. Greedy algorithms always give local optimum solutions but how Prim’s and Kru...

sandip_1999

691 views

sandip_1999 asked May 11, 2022

22 votes

3 answers

32

GATE CSE 2022 | Question: 39
Consider a simple undirected weighted graph $\textit{G},$ all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of $\textit{G}$ is/are $\text{TRUE}?$ The edge with the second smallest weight is ... always be part of any minimum spanning tree of $\textit{G}.$ $\textit{G}$ can have multiple minimum spanning trees.

Consider a simple undirected weighted graph $\textit{G},$ all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of $\...

Arjun

11.3k views

Arjun asked Feb 15, 2022

0 votes

1 answer

33

made easy test series - minimum spanning tree
How many minimum spanning trees are possible in this graph?

How many minimum spanning trees are possible in this graph?

atulcse

504 views

atulcse asked Jan 13, 2022

0 votes

1 answer

34

NPTEL Assignment Question
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change P only Q only Neither P nor Q Both P and Q

Let G be a weighted connected undirected graph with distinct positive edge weights.If every edge weight is increased by the same value, then which of the following statem...

rsansiya111

612 views

rsansiya111 asked Dec 7, 2021

5 votes

1 answer

35

Applied Test Series
Given the following undirected graph, the cost of the minimal spanning tree of the graph is ____.

Given the following undirected graph, the cost of the minimal spanning tree of the graph is ____.

LRU

675 views

LRU asked Nov 5, 2021

1 votes

1 answer

36

UGC NET CSE | December 2019 | Part 2 | Question: 6
The weight of minimum spanning tree in graph $G$, calculated using Kruskal’s algorithm is: $14$ $15$ $17$ $18$

The weight of minimum spanning tree in graph $G$, calculated using Kruskal’s algorithm is:$14$$15$$17$$18$

soujanyareddy13

2.0k views

soujanyareddy13 asked May 12, 2021

2 votes

1 answer

37

TIFR CSE 2021 | Part B | Question: 10
Let $G$ be a connected bipartite simple graph (i.e., no parallel edges) with distinct edge weights. Which of the following statements on $\text{MST}$ (minimum spanning tree) need $\text{NOT}$ be true? $G$ has a unique $\text{MST}$ ... edge. Every $\text{MST}$ in $G$ contains the third lightest edge. No $\text{MST}$ in $G$ contains the heaviest edge.

Let $G$ be a connected bipartite simple graph (i.e., no parallel edges) with distinct edge weights. Which of the following statements on $\text{MST}$ (minimum spanning tr...

soujanyareddy13

694 views

soujanyareddy13 asked Mar 25, 2021

20 votes

6 answers

38

GATE CSE 2021 Set 2 | Question: 1
Let $G$ be a connected undirected weighted graph. Consider the following two statements. $S_1$: There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$. $S_2$: If every edge in $G$ has distinct weight, then $G$ has a ... are true $S_1$ is true and $S_2$ is false $S_1$ is false and $S_2$ is true Both $S_1$ and $S_2$ are false

Let $G$ be a connected undirected weighted graph. Consider the following two statements.$S_1$: There exists a minimum weight edge in $G$ which is present in every minimum...

Arjun

11.9k views

Arjun asked Feb 18, 2021

8 votes

3 answers

39

GATE CSE 2021 Set 1 | Question: 17
Consider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is ___________.

Consider the following undirected graph with edge weights as shown:The number of minimum-weight spanning trees of the graph is ___________.

Arjun

11.0k views

Arjun asked Feb 18, 2021

0 votes

2 answers

40

UGC NET CSE | October 2020 | Part 2 | Question: 78
Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node $a$ ... $(a,b), (g,h), (g,f), (c,f), (c,i), (f,e), (b,c), (d,e)$

Consider the undirected graph below:Using Prim’s algorithm to construct a minimum spanning tree starting with node $a$, which one of the following sequences of edges re...

go_editor

1.8k views

go_editor asked Nov 20, 2020

38 votes

5 answers

41

GATE CSE 2020 | Question: 31
Let $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST ... $\Theta (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$

Let $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) ...

Arjun

19.1k views

Arjun asked Feb 12, 2020

4 votes

3 answers

42

GEEKS FOR GEEKS GATE 2017 MOCK
If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ? A O(m logn) B O(n) C O(m) D O(n logm)

If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list...

Hirak

3.6k views

Hirak asked Jun 9, 2019

1 votes

1 answer

43

MadeEasy Test Series 2019: Algorithms - Spanning Tree
Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume (u, v) are two vertices weight of a edge is =4lu- vl then the minimum cost of the spanning tree of G_ 36

Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume (u, v) are two vertices weight of a edge is =4lu- vl then the minimum cost of the...

Ram Swaroop

1.6k views

Ram Swaroop asked Jan 30, 2019

2 votes

1 answer

44

max weighted MST possible
Let G be a complete undirected graph on 5 vertices 10 edges, with weights being 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let X be the value of the maximum possible weight a MST of G can have. Then the value of x will be_____ the answer to this question is given as 11 but there is no procedure given . Please ,can anyone help me out in understanding the procedure

Let G be a complete undirected graph on 5 vertices 10 edges, with weights being 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let X be the value of the maximum possible weight a MST o...

Nandkishor3939

784 views

Nandkishor3939 asked Jan 25, 2019

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true