search
Log In

Recent questions tagged spanning-tree

3 votes
2 answers
1
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)$
asked Mar 31, 2020 in Algorithms Lakshman Patel RJIT 598 views
2 votes
2 answers
2
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 requires a ... to solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.
asked Sep 13, 2019 in Graph Theory gatecse 267 views
1 vote
1 answer
3
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
asked Jan 30, 2019 in Algorithms Ram Swaroop 657 views
0 votes
2 answers
5
1 vote
3 answers
6
For a complete graph with 10 vertices, The number of spanning trees is at least_____?
asked Aug 23, 2018 in Graph Theory Rishav Kumar Singh 291 views
2 votes
1 answer
7
How many edge disjoint spanning trees are possible for a undirected complete connected graph of n vertices?
asked Aug 13, 2018 in Algorithms Sambhrant Maurya 278 views
5 votes
1 answer
8
How do we come up with this formula for number of spanning tree of a n vertex complete graph Kn= $n^{n-2}$
asked Mar 18, 2018 in Algorithms Mahendra Singh Kanya 516 views
0 votes
4 answers
9
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?
asked Feb 19, 2018 in DS Parimal Paritosh 530 views
3 votes
1 answer
10
......................................................
asked Jan 28, 2018 in Algorithms Tuhin Dutta 334 views
2 votes
0 answers
12
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.
asked Jan 8, 2018 in Algorithms ankit_thawal 677 views
3 votes
0 answers
13
5 votes
1 answer
14
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.
asked Jan 2, 2018 in Algorithms sunil sarode 946 views
3 votes
1 answer
16
For a complete graph with 10 vertices, The number of spanning trees is at least_____?
asked Nov 17, 2017 in Graph Theory Parshu gate 929 views
4 votes
0 answers
17
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 number of spanning tree ... and $n^{m-1}m^{n-1}$ respectively. If anyone can state simple proof for above mentioned formula then it will great help.
asked Nov 15, 2017 in Graph Theory Chhotu 3.7k views
0 votes
2 answers
18
The total number of spanning trees that can be drawn using five labeled vertices is: 125 64 36 16
asked Sep 25, 2017 in DS rishu_darkshadow 1.3k views
0 votes
1 answer
19
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)$------------------ (1) Now in case ... $\log E$ =theta$(\log V)$.------------------(3) Can someone confirm if the 1 ,2 and the result of them i.e the 3rd equation is valid ?
asked Sep 16, 2017 in Algorithms rahul sharma 5 321 views
1 vote
1 answer
20
2 votes
2 answers
21
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
asked Sep 14, 2017 in Graph Theory Rakshit Gupta 505 views
1 vote
1 answer
22
How many Spanning Trees are possible from the graph given below? (a) 24 (b) 34 (c) 44 (d) 54
asked May 3, 2017 in Algorithms targate2018 1.8k views
1 vote
2 answers
23
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.
asked Mar 19, 2017 in Graph Theory dd 2k views
0 votes
1 answer
24
5 votes
2 answers
26
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.
asked Nov 30, 2016 in Algorithms makhdoom ghaya 853 views
1 vote
2 answers
27
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$
asked Oct 1, 2016 in DS makhdoom ghaya 501 views
...