# Recent questions tagged spanning-tree

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)$
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.
1 vote
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
4
5
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?
1 vote
6
For a complete graph with 10 vertices, The number of spanning trees is at least_____?
7
How many edge disjoint spanning trees are possible for a undirected complete connected graph of n vertices?
8
How do we come up with this formula for number of spanning tree of a n vertex complete graph Kn= $n^{n-2}$
1 vote
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?
10
......................................................
11
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.
13
Am getting 7. The answer given is 10. A - B , A - D , D - E , E - C are the edges i have included.
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.
1 vote
15
can someone provide a detailed solution of this??
16
For a complete graph with 10 vertices, The number of spanning trees is at least_____?
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.
18
The total number of spanning trees that can be drawn using five labeled vertices is: 125 64 36 16
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 ?
1 vote
20
True/False; 1. Every tree is spanning tree.
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
1 vote
22
How many Spanning Trees are possible from the graph given below? (a) 24 (b) 34 (c) 44 (d) 54
1 vote
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.
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.
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$