4.6 Minimum Spanning Tree

-

 v Spanning Tree: -

Ø A spanning tree is a subgraph of an undirected connected of Graph G, which has all the vertices along with minimum possible number of edges. Hence, a spanning tree does not have cycles and it also cannot be disconnected.

Ø If any vertex is missed, it is not a spanning tree.

Ø A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices.


Ø We have three spanning trees in one complete graph.

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

Ø In the above example, n is 3, hence 33-2 = 3 spanning trees are possible.

 

Minimum Spanning Tree (MST): -

Ø A minimum spanning tree is a spanning tree, which the sum of the weights of the edge has minimum weight than all other spanning trees of the same graph.

Ø The weight of the spanning tree is the sum of the weights given to the edges of the spanning tree.

Ø In real-world situations, this weight can be measured as distance, congestion, traffic load or any random value denoted to the edges.

Example: Undirected-connected-weighted Graph

    

Ø The sum of the edges of the above graph is 6+5+2+3 = 16. Now, some of the possible spanning trees created from the above graph are


Ø The first spanning tree is a tree in which we have removed the edge between the vertices B and D.

Ø The sum of the edges of the first spanning tree is : 5 + 6 + 3 = 14.


Ø The second spanning tree is a tree in which we have removed the edge between the vertices A and B.

Ø The sum of the edges of the Second spanning tree is : 6 + 3 + 2 = 11.


Ø The third spanning tree is a tree in which we have removed the edge between the vertices C and D.

Ø The sum of the edges of the third spanning tree is : 5 + 6 + 2 = 13.


Ø The fourth spanning tree is a tree in which we have removed the edge between the vertices A and C.

Ø The sum of the edges of the fourth spanning tree is : 5 + 2 + 2 = 10.


Ø So, the minimum spanning tree that is selected from the above spanning trees for the given weighted graph is -


Applications of spanning tree: -

·        Computer Network Routing Protocol.

·        Cluster Analysis.

·        Civil Network Planning.

 

Applications of minimum spanning tree: -

·        To find paths in the map.

·        To design networks like telecommunication networks, water supply networks, and electrical grids.







































Popular posts from this blog

operators in c programming

-
Image
v Operators: - An operator is a symbol that tells or intimates to the compiler to perform specific calculations or manipulations on one or more operands. Operators are essential for performing computations and making decisions in programs.   a + b is an operation a & b are operands + is an operator   Based on number of operands involved: 1.      Unary operators: - unary operators can be applied on only one operator. Example: -   ++ , -- , - (unary minus) , sizeof , ~ (compliment) , ! (not).   2.      Binary operators: - binary operators can be applied on two operands. Example: -   + , -,   * , / , etc.   3.    Ternary operators: - Ternary operator can be applied on three operands. Example: -   ?: (ternary conditional operator).   C supports several operators, can be classified into following...
Read more

2.4 Arrays in c programming

-
Image
  Arrays: - An array is a collection of elements of the same data type stored in contiguous memory locations. It is a derived data type and a homogenous data structure. It is a variable which can store multiple values of the same type under a single variable name, making it easier to manage and manipulate related data. The size of an array is fixed. To access the elements of an array, we use indexes or subscripts accordingly. array index or subscript is used to identify array elements address. Array index or subscript starts with 0 to n-1.   Declaration of an array: - The declaration of an array means telling the compiler to create an array variable and reserving memory for a fixed number of elements of the same data type. Initialization of an array: - Initializing an array means assigning initial values to its elements. Types of arrays: - Arrays are classified based on the number of dimensions they have:             ...
Read more

Variables in c

-
Image
  Variables: - A variable is a data name or an identifier which stores a value that can be changed during the program execution.  Every variable might belong to any of the data types, like int, float, char, etc.  The name of a variable can be composed of letters, digits, and the underscore character. It must begin with either a letter or an underscore.  Variables are case-sensitive because uppercase and lowercase letters are distinct. C programming language also allows defining various other types of variables, like numeric array, character array, pointer, Structure, Union, Enumeration and etc.               Example: - sum, height, _value Declaring a variable in C: - Variable declaration means telling the compiler about the name and type of a variable before using it in the program. Variable declaration is the process of reserving a memory location and defining the type of data that will be stored in that locatio...
Read more