Dark Mode

Recent questions tagged spanning-tree

0 votes

1 answer

1

UGCNET CSE December 2022: 28
Consider the Graph below: How many spanning trees can be found? $10$ $5$ $9$ $8$ (Option $1 [39409]) 1$ (Option $2[39410]) 2$ (Option $3 [39411]) 3$ (Option $4 [39412]) 4$ Answer Given by Candidate : $2$

admin asked in Algorithms May 20, 2023

by admin

531 views

0 votes

0 answers

2

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

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

by Çșȇ ʛấẗẻ

360 views

0 votes

0 answers

3

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

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

by Çșȇ ʛấẗẻ

232 views

0 votes

0 answers

4

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

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

by Çșȇ ʛấẗẻ

324 views

1 vote

1 answer

5

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

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

by Çșȇ ʛấẗẻ

420 views

22 votes

3 answers

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

11.2k views

20 votes

3 answers

7

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

7.4k views

5 votes

2 answers

8

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)$

admin asked in Algorithms Mar 31, 2020

by admin

1.8k views

4 votes

2 answers

9

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

776 views

1 vote

2 answers

10

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

482 views

1 vote

1 answer

11

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

0 votes

3 answers

12

Ace test series question on number of spanning trees possible

Shankar Kakde asked in Algorithms Jan 24, 2019

by Shankar Kakde

968 views

0 votes

0 answers

13

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

503 views

0 votes

0 answers

14

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

751 views

0 votes

1 answer

15

Churchill Khangar asked in Algorithms Nov 22, 2018

by Churchill Khangar

551 views

0 votes

2 answers

16

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

750 views

1 vote

3 answers

17

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

Rishav Kumar Singh asked in Graph Theory Aug 22, 2018

by Rishav Kumar Singh

941 views

2 votes

1 answer

18

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

640 views

0 votes

1 answer

19

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

440 views

5 votes

1 answer

20

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

1 vote

4 answers

21

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

1.2k views

7 votes

1 answer

22

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

2.2k views

7 votes

2 answers

23

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 Bhaiya asked in Algorithms Jan 15, 2018

by Lakshman Bhaiya

6.0k views

2 votes

0 answers

24

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

1.2k views

3 votes

0 answers

25

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

529 views

5 votes

1 answer

26

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

2.0k views

1 vote

0 answers

27

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

Kalpataru Bose asked in Algorithms Dec 31, 2017

by Kalpataru Bose

692 views

Page:

1
2
3
next »

Recent questions tagged spanning-tree