Dark Mode

Recent questions tagged spanning-tree

0 votes

0 answers

1

self doubt
Determine the number of spanning tree in the following graph ?

Çșȇ ʛấẗẻ asked in Algorithms Mar 10

by Çșȇ ʛấẗẻ

48 views

0 votes

0 answers

2

Self Doubt
Determine the number of the spanning treess in the following graph ???

Çșȇ ʛấẗẻ asked in Algorithms Mar 10

by Çșȇ ʛấẗẻ

28 views

0 votes

0 answers

3

Self doubt
Determine the number of the spanning treess in the following graph ???

Çșȇ ʛấẗẻ asked in Algorithms Mar 10

by Çșȇ ʛấẗẻ

21 views

1 vote

1 answer

4

Spanning Tree
Determine the number of the spanning treess in the following graph ???

Çșȇ ʛấẗẻ asked in Algorithms Mar 10

by Çșȇ ʛấẗẻ

57 views

12 votes

1 answer

5

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.1k views

11 votes

2 answers

6

GATE CSE 2022 | Question: 48
Let $\textit{G(V,E)}$ be a directed graph, where $\textit{V} = \{ 1, 2, 3, 4, 5 \}$ is the set of vertices and $\textit{E}$ is the set of directed edges, as defined by the following adjacency matrix $\textit{A}.$ ... contains a directed path from $r$ to every other vertex in $V.$ The number of such directed spanning trees rooted at vertex $5$ is __________________.

Arjun asked in Algorithms Feb 15, 2022

by Arjun

3.4k views

5 votes

2 answers

7

NIELIT 2016 DEC Scientist B (IT) - Section B: 27
Complexity of Kruskal's algorithm for finding minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is: $O(mn)$ $O(m)$ $O(m+n)$ $O(n)$

Lakshman Patel RJIT asked in Algorithms Mar 31, 2020

by Lakshman Patel RJIT

1.4k views

4 votes

2 answers

8

CMI2019-A-7
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match ... solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.

gatecse asked in Graph Theory Sep 13, 2019

531 views

1 vote

2 answers

9

KPGCET-CSE-2019-33
The least running time of creating spanning tree from connected graph in G(E, V) is O (V log V) O (E + V log V) O (E log V) O (V log V + E log V) Where E, V are respectively number of edges & vertices in the graph.

gatecse asked in Algorithms Aug 4, 2019

276 views

1 vote

1 answer

10

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

Ram Swaroop asked in Algorithms Jan 30, 2019

1.3k views

0 votes

3 answers

11

Ace test series question on number of spanning trees possible

Shankar Kakde asked in Algorithms Jan 24, 2019

by Shankar Kakde

709 views

0 votes

0 answers

12

made easy 2019
consider a graph G given below, if the edges are having weight 1,2,3,4,5,6,7,8,9,10; then maximum possible weight a minimum weight spanning tree of G can have is according to me MST can have weight=10; what they are asking is about second minimum spanning tree; which according to me can have weight 11 i already searched but didnt find duplicate of this question !

Gate Fever asked in Algorithms Dec 2, 2018

328 views

0 votes

0 answers

13

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 2, 2018

528 views

0 votes

1 answer

14

Churchill Khangar asked in Algorithms Nov 22, 2018

by Churchill Khangar

269 views

0 votes

2 answers

15

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

589 views

1 vote

3 answers

16

Doubt
For a complete graph with 10 vertices, The number of spanning trees is at least_____?

Rishav Kumar Singh asked in Graph Theory Aug 23, 2018

by Rishav Kumar Singh

604 views

2 votes

1 answer

17

Made Easy algorithms
How many edge disjoint spanning trees are possible for a undirected complete connected graph of n vertices?

Sambhrant Maurya asked in Algorithms Aug 13, 2018

by Sambhrant Maurya

499 views

0 votes

1 answer

18

me wk book
let T be a minimum cost spanning tree of G. suppose that ewe decreased the weight of one of the edge in T.then to check modified T is MST or not how much tym will take??? O(1) or O(n)?????

eyeamgj asked in Algorithms Jun 16, 2018

237 views

5 votes

1 answer

19

Number of spanning tress
How do we come up with this formula for number of spanning tree of a n vertex complete graph Kn= $n^{n-2}$

Mahendra Singh Kanya asked in Algorithms Mar 18, 2018

by Mahendra Singh Kanya

1.1k views

1 vote

4 answers

20

trees
Given a preorder, postorder and inorder traversal of a tree, is it always possible to obtain a tree that satisfies each of the three conditions? Or is it possible to not obtain a tree at all?

Parimal Paritosh asked in DS Feb 19, 2018

by Parimal Paritosh

898 views

7 votes

2 answers

21

Number of minimum spanning trees
The number of distinct minimum spanning trees for the weighted graph shown below is ___________.

vishal chugh asked in Graph Theory Jan 18, 2018

by vishal chugh

1.8k views

7 votes

2 answers

22

number of spanning tree
Consider a complete bipartite graph with ‘m’ and ‘n’ vertices. If m = 4, n = 4, then the number of spanning trees of graph are ________.

Lakshman Patel RJIT asked in Algorithms Jan 15, 2018

by Lakshman Patel RJIT

4.6k views

2 votes

0 answers

23

TEST SERIES
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges to which they are added to construct Minimum Spanning Tree (MST)? P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T PLEASE EXPLAIN.

ankit_thawal asked in Algorithms Jan 8, 2018

by ankit_thawal

997 views

3 votes

0 answers

24

Ace Test series: Algorithms - Spanning Tree
Am getting 7. The answer given is 10. A - B , A - D , D - E , E - C are the edges i have included.

smsubham asked in Algorithms Jan 6, 2018

405 views

5 votes

1 answer

25

How many MST is possible?
Given graph using Prim’s or Kruskal’s algorithm, find out that how many distinct minimum cost spanning trees are possible___? My answer was 1 and given is 2 ,what I am missing ? Edit:I had confirmed with it and answer is only one tree possible.

sunil sarode asked in Algorithms Jan 2, 2018

by sunil sarode

1.5k views

1 vote

0 answers

26

MadeEasy Test Series: Algorithms - Spanning Tree
can someone provide a detailed solution of this??

Kalpataru Bose asked in Algorithms Jan 1, 2018

by Kalpataru Bose

564 views

3 votes

2 answers

27

Spannig trees
For a complete graph with 10 vertices, The number of spanning trees is at least_____?

Parshu gate asked in Graph Theory Nov 17, 2017

2.0k views

Page:

1
2
3
next »

Recent questions tagged spanning-tree