TCS Papers: Sample Questions 214 - 214 of 502

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

Question number: 214

» Basic CS » Data Structures

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

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