# TCS Papers: Sample Questions 214 - 214 of 502

Examrace Placement Series prepares you for the toughest placement exams to top companies.

## Question number: 214

Essay Question▾

### 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, multi-terminal minimum cut problem and minimum-cost 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. Image of the Spanning Tree Given the image is define the spanning trees
• In the figure above, there are three spanning trees or one complete graph.

## Properties of Spanning Tree

• A complete undirected graph can have maximum nn-2 number of spanning trees, where n is the number of nodes.

• In the above addressed example, 33−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 n-1 edges