Dark Mode

Recent questions tagged minimum-spanning-tree

1 vote

1 answer

1

GO Classes 2023 | IIITH Mock Test 3 | Question: 15
Consider a undirected graph $G$ with $n$ vertices and every edge weight being distinct. Edge $e_1$ is edge with minimum weight and edge $e_2$ is edge with maximum weight. Then, which of the following is/are FALSE? (Mark all the ... No minimum spanning tree contains $e_2$ $G$ has a unique minimum spanning tree if $e_2$ is in a minimum spanning tree

GO Classes asked in Algorithms Apr 15

226 views

2 votes

1 answer

2

GO Classes 2023 | IIITH Mock Test 2 | Question: 64
The following diagram shows the set of edges (in thick black lines) selected at some intermediate step of an MST algorithm. Lighter edges are not yet in MST. Assume that we got above the intermediate state using Kruskal’s algorithm. What would be the maximum value of $x+y-z ?$ $100$ $110$ $120$ $130$

GO Classes asked in Algorithms Apr 8

308 views

1 vote

2 answers

3

GO Classes 2023 | IIITH Mock Test 1 | Question: 11
Suppose that a MST of the following edge-weighted graph contains the edges with weights $x, y$, and $z$. What will be the maximum value of $x+y+z?$ $200$ $250$ $300$ $350$

GO Classes asked in Algorithms Mar 26

299 views

0 votes

1 answer

4

TestBook testseries question to find max weight of MST
A complete graph G with 5 nodes has positive weight edges, each node has a distinct weight with an integer value and maximum weight is equal to number of edges in G. What can be the maximum weight of minimum spanning tree for graph G?

Sahil_Lather asked in Algorithms Jan 28

by Sahil_Lather

186 views

2 votes

0 answers

5

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?

sandip_1999 asked in Algorithms May 11, 2022

316 views

12 votes

1 answer

6

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.

Arjun asked in Algorithms Feb 15, 2022

by Arjun

6.7k views

0 votes

1 answer

7

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

atulcse asked in Algorithms Jan 13, 2022

370 views

0 votes

1 answer

8

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

rsansiya111 asked in Algorithms Dec 7, 2021

372 views

5 votes

1 answer

9

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

LRU asked in Algorithms Nov 5, 2021

by LRU

434 views

Page:

1
2
3
4
5
6
next »

Recent questions tagged minimum-spanning-tree