इस ट्यूटोरियल में, आप उदाहरणों और बिंबों की मदद से फैले पेड़ और न्यूनतम फैले पेड़ के बारे में जानेंगे।
इससे पहले कि हम पेड़ों को फैलाने के बारे में जानें, हमें दो रेखांकन समझने की जरूरत है: अप्रत्यक्ष रेखांकन और जुड़े हुए रेखांकन।
एक अप्रत्यक्ष ग्राफ़ एक ऐसा ग्राफ़ है जिसमें किनारों को किसी भी दिशा में इंगित नहीं किया जाता है (यानी किनारों को द्विदिश किया जाता है)।
अप्रत्यक्ष ग्राफ़
एक जुड़ा हुआ ग्राफ एक ग्राफ है जिसमें हमेशा एक शीर्ष से किसी भी अन्य शीर्ष पर जाने का मार्ग होता है।
जुड़ा हुआ ग्राफ
फैले हुए वृक्ष
एक फैले हुए वृक्ष एक अप्रत्यक्ष रूप से जुड़े ग्राफ का उप-ग्राफ है, जिसमें न्यूनतम संभव संख्या के किनारों के साथ ग्राफ के सभी कोने शामिल हैं। यदि एक शीर्ष याद किया जाता है, तो यह एक फैले हुए पेड़ नहीं है।
किनारों को भार सौंपा जा सकता है या नहीं भी हो सकता है।
nएक पूर्ण ग्राफ़ से बनाए जा सकने वाले वर्टिस वाले पेड़ों की कुल संख्या के बराबर है ।n(n-2)
यदि हमारे पास है n = 4, तो अधिकतम फैले पेड़ों की संख्या बराबर है । इस प्रकार, 16 फैले हुए वृक्षों को एक पूर्ण ग्राफ से 4 कोने के साथ बनाया जा सकता है।44-2 = 16
एक स्पैनिंग ट्री का उदाहरण
आइए नीचे दिए उदाहरणों के साथ फैले पेड़ को समझें:
मूल ग्राफ होने दें:
सामान्य ग्राफ
उपरोक्त ग्राफ से बनाए जा सकने वाले कुछ संभावित पेड़ हैं:
एक फैले हुए पेड़ 
एक फैले हुए पेड़ 
एक फैले हुए पेड़ 
एक फैले हुए पेड़ 
एक फैले हुए पेड़ 
एक फैले हुए पेड़
न्यूनतम फैलाव वाला पेड़
न्यूनतम फैले हुए पेड़ एक फैले हुए पेड़ हैं जिसमें किनारों के वजन का योग यथासंभव न्यूनतम होता है।
एक स्पैनिंग ट्री का उदाहरण
आइए नीचे दिए गए उदाहरण की मदद से उपरोक्त परिभाषा को समझते हैं।
प्रारंभिक ग्राफ है:
भारित ग्राफ
उपरोक्त ग्राफ से संभावित फैले हुए पेड़ हैं:
न्यूनतम फैले हुए पेड़ - 1 
न्यूनतम फैले हुए पेड़ - 2 
न्यूनतम फैले हुए पेड़ - 3 
न्यूनतम फैले हुए पेड़ - 4
उपरोक्त फैले पेड़ों से न्यूनतम फैले पेड़ हैं:
न्यूनतम फैलाव वाला पेड़
ग्राफ से न्यूनतम फैले हुए पेड़ को निम्नलिखित एल्गोरिदम का उपयोग करते हुए पाया जाता है:
- प्राइम का एल्गोरिथम
- क्रुस्कल का एल्गोरिदम
स्पानिंग ट्री एप्लीकेशन
- कंप्यूटर नेटवर्क रूटिंग प्रोटोकॉल
- क्लस्टर विश्लेषण
- सिविल नेटवर्क योजना
न्यूनतम स्पानिंग ट्री एप्लीकेशन
- नक्शे में पथ खोजने के लिए
- दूरसंचार नेटवर्क, जल आपूर्ति नेटवर्क और विद्युत ग्रिड जैसे नेटवर्क डिजाइन करने के लिए।
