Spanning Tree and Minimum Spanning Tree

Spanning Tree (स्पेनिंग ट्री):-

A spanning tree is a subset of Graph G={V,E} which connects all of the vertices with minimum possible number of edges and It looks like a tree. In other words every connected and un-directed graph G has at least one spanning tree. Disconnected graph doesn't have any spanning tree as it can't be spanned at all its vertices.   

General properties of spanning tree:-

1.) A spanning tree does not have any cycle and it must be a connected graph. 

2.) A spanning tree will have n nodes and n-1 edges.

3.) Every connected graph G can have more than one spanning tree.

4.) All possible spanning trees of graph G has same number of edges and vertices.

5.) A complete connected un-directed graph G of n vertices can have maximum n$(n-2) spanning trees.  

6.) If we remove an edge from spanning tree then it will be converted in to disconnected graph.

7.) If we add an edge in spanning tree then it will make a cycle or loop.

एक स्पेनिंग ट्री ग्राफ G={V,E} का एक समुच्चय होता है जो कम से कम एजेस की सहायता से ग्राफ के सभी बिन्दुओ को जोड़ता है एवं ट्री के समान दिखाई देता है। दुसरे शब्दों में प्रत्येक कनेक्टेड एवं अनडायरेक्टेड ग्राफ G में कम से कम एक स्पेनिंग ट्री होता है। डिसकनेक्टेड ग्राफ में स्पेनिंग ट्री नहीं हो सकता है क्यूंकि यह ग्राफ के सभी बिन्दुओ को आपस में नहीं जोड़ता है।

स्पेनिंग ट्री की विशेषताएँ:-

1.) एक स्पेनिंग ट्री में कोई साइकिल नहीं होता है एवं यह कनेक्टेड ग्राफ होता है।

2.) एक स्पेनिंग ट्री में n नोड्स एवं n-1 एजेस होगी। 

3.) प्रत्येक कनेक्टेड ग्राफ G में एक या अधिक स्पेनिंग ट्री उपस्थित हो सकते है।

4.) किसी ग्राफ के सभी स्पेनिंग ट्री में एजेस की संख्या एक समान होती है।

5.) n बिन्दुओ वाले कम्पलीट कनेक्टेड अनडायरेक्टेड ग्राफ G में अधिकतम n$(n-2) स्पेनिंग ट्री हो सकते है।

6.) यदि स्पेनिंग ट्री से एक एज को हटा दिया जाता है तब वह डिसकनेक्टेड ग्राफ बन जाता है।

7.) यदि स्पेनिंग ट्री से एक एज को जोड़ दिया जाता है तब वह साइकिल या लूप बन जाता है। 

Minimum Spanning Tree (मिनिमम स्पेनिंग ट्री):-

If a weighted graph G={V,E} then the spanning tree with the lowest total edge weights is called the minimum spanning tree.

यदि एक वेटेड ग्राफ G={V,E} है तब उसका एक स्पेनिंग ट्री, जिसकी एजेस का कुल वेट(वजन) सबसे कम होता है,  मिनिमम स्पेनिंग ट्री कहलाता है।  

Minimum spanning trees are used in network designing, cluster analysis and routing protocols etc.

मिनिमम स्पेनिंग ट्री का प्रयोग नेटवर्क डिजाइनिंग,क्लस्टर एनालिसिस एवं रूटिंग प्रोटोकॉल्स इत्यादि में किया जाता है।