TCS Papers: Sample Questions 214  214 of 502
Examrace Placement Series prepares you for the toughest placement exams to top companies.
Question number: 214
Describe in Detail
What is a spanning tree?
Explanation

A spanning tree is associated with a network where all the nodes of the graph appear on the tree once.

A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.

The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees of a graph.

Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.

Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multiterminal minimum cut problem and minimumcost weighted perfect matching.

Spanning trees are a subset of connected Graph G and disconnected graphs do not have spanning tree.

Thus, a spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges a spanning tree does not have cycles and it cannot be disconnected.

Every connected and undirected Graph G thus has at least one spanning tree but a disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices.


In the figure above, there are three spanning trees or one complete graph.
Properties of Spanning Tree

A complete undirected graph can have maximum n^{n2} number of spanning trees, where n is the number of nodes.

In the above addressed example, 3^{3−2} = 3 spanning trees are possible.

From a complete graph, by removing maximum e  n + 1 edges, we can construct a spanning tree.

Spanning tree with n nodes has n1 edges