Dark Mode

Recent questions tagged spanning-tree

3 votes

2 answers

31

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

Parshu gate asked in Graph Theory Nov 16, 2017

2.4k views

4 votes

0 answers

32

Number of spanning Trees
Hi, As all of us knows number of spanning tree of simple labeled graph could be computed by the Kirchhoff's theorem. But is there any other method (other than Brute force) to compute the number of spanning tree of given general graph ? Formula for ... respectively. If anyone can state simple proof for above mentioned formula then it will great help.

Chhotu asked in Graph Theory Nov 15, 2017

by Chhotu

5.4k views

1 vote

3 answers

33

UGC NET CSE | December 2008 | Part 2 | Question: 3
The total number of spanning trees that can be drawn using five labeled vertices is: 125 64 36 16

rishu_darkshadow asked in DS Sep 25, 2017

by rishu_darkshadow

3.8k views

0 votes

1 answer

34

Basic Doubt in spanning tree complexity
Let us say Simple graph has V vertices and E edges. Now i am trying to find relation between E and V. If it is a complete graph ,then E=V(V-1)/2, => E=$c.V^2$ => E=$O(V^2)$ => taking log of both sides. => $\log E$=$O(\log V)$-- ... .------------------(3) Can someone confirm if the 1 ,2 and the result of them i.e the 3rd equation is valid ?

rahul sharma 5 asked in Algorithms Sep 16, 2017

by rahul sharma 5

716 views

1 vote

1 answer

35

[Discrete maths] Spanning trees
True/False; 1. Every tree is spanning tree.

rahul sharma 5 asked in Graph Theory Sep 16, 2017

by rahul sharma 5

730 views

2 votes

2 answers

36

Graph Theory
Consider a 'reversed Kruskal' Algorithm for computing a MST. Initialize T to be the set of all edges in the graph. Now consider edges from largest to smallest cost. For each edge, delete it from T if that edge belongs to a cycle in T. Assuming all the edge costs are distinct, does this new algorithm correctly compute a MST? a) Yes b) no c) cant say

Rakshit Gupta asked in Graph Theory Sep 13, 2017

by Rakshit Gupta

1.3k views

1 vote

3 answers

37

No of spanning Trees
Let $K_n$ denote the complete undirected graph with $n$ vertices where n is an even number. Find the maximum number of spanning trees of $K_n$ that can be formed in such a way that no two of these spanning trees have a common edge.

dd asked in Graph Theory Mar 19, 2017

by dd

5.5k views

0 votes

1 answer

38

Sarvottam Patel asked in Theory of Computation Feb 7, 2017

by Sarvottam Patel

466 views

0 votes

3 answers

39

Virtual Gate Test Series: Algorithms - Minimum Spanning Tree
I think all options are wrong

Purple asked in Algorithms Jan 11, 2017

by Purple

1.1k views

12 votes

4 answers

40

GATE CSE 1989 | Question: 4-vii
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.

makhdoom ghaya asked in Algorithms Nov 30, 2016

by makhdoom ghaya

2.7k views

4 votes

1 answer

41

Spanning Trees
Consider the following adjacency matrix representation of connected graph then find the number of spanning trees are possible for the given graph $\begin{bmatrix} 0&1&1&1&0 \\ 1&0&1&1&0 \\1&1&0&0&1 \\ 1&1&0&0&1 \\0&0&1&1&0 \end{bmatrix}$

Rohan Mundhey asked in Algorithms Nov 11, 2016

by Rohan Mundhey

1.3k views

1 vote

4 answers

42

UGC NET CSE | August 2016 | Part 3 | Question: 33
Consider a weighted complete graph $G$ on the vertex set $\left\{ν_{1} , ν_{2},.... ν_{n} \right\}$ such that the weight of the edge $(ν_{i} , ν_{j})$ is $4 | i – j|$. The weight of minimum cost spanning tree of $G$ is : $4n^{2}$ $n$ $4n – 4$ $2n – 2$

makhdoom ghaya asked in DS Oct 1, 2016

by makhdoom ghaya

1.8k views

2 votes

1 answer

43

#spanningtree
What is the upper bound on the number of edge disjoint spanning trees in a complete graph of n vertices. a. n b. n-1 c. n/2 d. n/3

saurabh rai asked in Algorithms Aug 27, 2016

586 views

1 vote

1 answer

44

Spanning trees
Find the number of spanning trees in the following graph;

Amit puri asked in Algorithms Aug 22, 2016

3.0k views

0 votes

1 answer

45

Virtual Gate Test Series: Algorithms - Spanning Tree

debanjan sarkar asked in Algorithms Jul 15, 2016

by debanjan sarkar

587 views

7 votes

5 answers

46

ISRO2015-41
The number of spanning trees for a complete graph with seven vertices is $2^5$ $7^5$ $3^5$ $2^{2 \times 5}$

shivanisrivarshini asked in Algorithms Jun 5, 2016

by shivanisrivarshini

6.8k views

1 vote

0 answers

47

ISI2012-PCB-CS-4
A fan of order $n$ is a graph on the vertices $\{0, 1, \dots, n\}$ with $2n − 1$ edges defined as follows: vertex $0$ is connected by an edge to each of the other $n$ vertices, and vertex $i$ ... the number of spanning trees of the fan of order $n$. Calculate $f_4$. Write a recurrence for $f_n$. Solve for fn using ordinary generating functions.

go_editor asked in Graph Theory Jun 2, 2016

684 views

1 vote

1 answer

48

ISI2014-PCB-CS-3b
Let $G = (V, E)$ be an undirected weighted graph with all edge weights being positive. Design an efficient algorithm to find the maximum spanning tree of $G$.

go_editor asked in Algorithms May 31, 2016

688 views

2 votes

1 answer

49

CMI2015-A-04a
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows ... a spanning tree with minimum number of edges Find a minimal coloring Find a minimum size vertex cover Find a maximum size independent

go_editor asked in Graph Theory May 27, 2016

809 views

0 votes

1 answer

50

Upper bound on the number of edge disjoint spanning trees in a complete graph of n vertices?

gshivam63 asked in Algorithms May 19, 2016

2.9k views

37 votes

5 answers

51

GATE CSE 2010 | Question: 51
Consider a complete undirected graph with vertex set $\{0, 1, 2, 3, 4\}$. Entry $W_{ij}$ in the matrix $W$ below is the weight of the edge $\{i, j\}$ ... weight of a path $P$ from vertex $1$ to vertex $2$ in this graph such that $P$ contains at most $3$ edges? $7$ $8$ $9$ $10$

go_editor asked in Algorithms Apr 21, 2016

14.8k views

40 votes

6 answers

52

GATE CSE 2011 | Question: 55
An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid i-j\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below. The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n=10$ is $11$ $25$ $31$ $41$

go_editor asked in Algorithms Apr 21, 2016

11.7k views

117 votes

6 answers

53

GATE CSE 2016 Set 1 | Question: 40
$G=(V, E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spanning trees $(MSTs)$ of $G$ is/are TRUE? If $e$ is the lightest edge of some ... some cycle in $G$, then every MST of $G$ excludes $e$. I only. II only. Both I and II. Neither I nor II.

Sandeep Singh asked in Algorithms Feb 12, 2016

by Sandeep Singh

26.1k views

85 votes

18 answers

54

GATE CSE 2016 Set 1 | Question: 39
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________

Sandeep Singh asked in Algorithms Feb 12, 2016

by Sandeep Singh

35.3k views

62 votes

8 answers

55

GATE CSE 2016 Set 1 | Question: 14
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$

Sandeep Singh asked in Algorithms Feb 12, 2016

by Sandeep Singh

22.5k views

0 votes

0 answers

56

Calculation of the number of spanning trees
Hi,I just encountered problems about calculation of the number of spanning trees,like this one: https://gateoverflow.in/10154/find-out-the-no-of-spanning-tree-possible I am able to proceed to choose the number of edges.But I am ... calculation of large determinants for such problem,which is not feasible.Are you aware of any other method to do the same?

Rachit Saxena asked in Algorithms Dec 9, 2015

by Rachit Saxena

572 views

11 votes

3 answers

57

find out the no. of spanning tree possible
How many spanning trees are possible from the graph given below? $24$ $34$ $44$ $54$

Gunjan Rathore asked in Algorithms May 2, 2015

by Gunjan Rathore

4.7k views

44 votes

5 answers

58

GATE CSE 2015 Set 3 | Question: 40
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is increased by five, the weight of a minimum spanning tree becomes ______.

go_editor asked in Algorithms Feb 15, 2015

10.8k views

70 votes

5 answers

59

GATE CSE 2015 Set 1 | Question: 43
The graph shown below has $8$ edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight $36$ and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only ... which are in the MST are given in the figure shown below. The minimum possible sum of weights of all $8$ edges of this graph is_______________.

makhdoom ghaya asked in Algorithms Feb 13, 2015

by makhdoom ghaya

17.6k views

0 votes

3 answers

60

Minimum cost spanning tree
Please explain why the answer is a)

dhingrak asked in Algorithms Dec 12, 2014

806 views

Page:

Recent questions tagged spanning-tree