Spanning Tree
first we have to read about sub graphs, connected graph and complete graph to know what is spanning tree.
Sub-graphs :- A graph whose vertices and edges are subsets of another graph.
Example:- We have a graph G1 like in the image.
So, here are many sub-graphs in this graph
Example of sub-Graphs from the above graph G1.
S1 and S2 are the sub-graph of graph G1. Here are other sub-graphs also exists from the G1 graph.
Connected Graph :- A connected graph is graph that is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph. A graph that is not connected is said to be disconnected.
example :- if we can travel from any node to another node in a graph is called connected graph like in graph G1, I have to visit node 6 from node 0 than first I’ll move towards node 3 from 0 than i’ll move to node 4 from node 3 and than finally i can reach node 6 from the node 4 that means its a connected graph.
Complete Graph :- A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.in simple language if every node is connect to all other nodes in graph with unique edges is called complete graph.
example :-
so as you can see in above example every node of graph is connected to all other nodes of graph.
now we’ll move further to Spanning Tree
Spanning Tree :- A connected Sub-graph of graph is said to be spanning tree of graph iff(if and only if):-
- All vertices of Graph must be present in sub-graph.
- Number of edges in sub-graph should be V-1 here V is the no. of vertices in Graph.
Example:-
so as you can see in above example that every spanning tree is a sub-graph of main graph and also these spanning trees are connected graph too and then
both condition are full filled which mention above.
