A spanning tree is known as a subgraph of an undirected connected graph that possesses all of the graph’s edges or vertices with the rarest feasible edges. If a vertex is missing, then it is not a spanning tree. To understand the spanning tree, it is important to learn more about graphs. Learn more about graphs and its applications in detail.
Table of Contents
- Graph
- More about Spanning Tree
- Example of Spanning Tree
- Applications of the Spanning Tree
- Properties of Spanning Tree
- Practice Problems
Graph
A graph can be represented as a collection of vertices with edges joining them. The most popular types of graphs:
- Undirected Graph: An undirected graph is one where the edges do not indicate in the same direction, making it bidirectional instead of unidirectional. It’s also feasible to consider it as a graph with V vertices and E edges, each uniting two separate vertices.
- Connected Graph: A connected graph is one when there is invariably a path from one vertex to another. Also, we can say that a graph is connected if we can go to any vertex from any different vertex by pursuing edges in either direction.
- Directed Graph: A graph is considered a directed graph if all the edges present between any nodes or vertices have a defined direction.
Read more here about: Graph and its applications.
More about Spanning Tree
A complete undirected graph possesses n(n-2) number of spanning trees, so if we have n = 4, the highest number of potential spanning trees is equivalent to 44-2 = 16. Thus, 16 spanning trees can be constructed from a complete graph with 4 vertices.
Example of Spanning Tree
Now, let’s walk through the below example and try to understand the spanning tree and how it works:
Let the real graph be:
The following are some examples of spanning trees that can be generated from the graph above:
Applications of the Spanning Tree
A spanning tree is preferred to discover the shortest path to link all nodes of the graph. In this section, we will discuss some of the most famous and common applications of the spanning tree:
- A spanning tree is very helpful in the civil network zone and planning.
- It is used in network routing protocol.
Properties of Spanning Tree
Properties of the spanning tree are as follows:
- A connected graph G can have more than one spanning tree.
- There are no loops or cycles in a spanning tree.
- As a spanning tree is loosely connected, if you remove one edge from the tree, it will disconnect the graph.
- Because a spanning tree is most acyclic, adding one edge will result in a loop.
- The total number of edges in a spanning tree is n-1, where n represents the number of nodes.
- If the graph is complete, the spanning tree can be produced by destroying the maximum (e-n+1) edges, where ‘e’ denotes the number of edges and ‘n’ denotes the number of vertices.
Practice Problems
Q1. Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes _______.
Q2. Consider the directed graph given below.
Which one of the following is TRUE?
1) The graph does not have any topological ordering
2) Both PQRS and SRQP are topological orderings
3) Both PSRQ and SPRQ are topological orderings
4) PSRQ is the only topological ordering
Q3. The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ________.
Q4. Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj)|1≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i – j|. The weight of the minimum spanning tree of G is ______.
Q5. Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x ϵ V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) – d(v)?
1) -1
2) 0
3) 1
4) 2
Q6. Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance 4 from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _______.
Q7. Consider the graph shown below:
Use Kruskal’s algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is
1) 13
2) 16
3) 17
4) 14
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.
Also Explore,
