डेटा संरचना और एल्गोरिदम - स्पैनिंग ट्री
एक फैले हुए पेड़ ग्राफ जी का एक उपसमुच्चय है, जिसमें सभी कोनों को न्यूनतम संभव किनारों के साथ कवर किया गया है। इसलिए, एक फैले हुए पेड़ में चक्र नहीं होते हैं और इसे काट नहीं किया जा सकता है।
इस परिभाषा के द्वारा, हम एक निष्कर्ष निकाल सकते हैं कि हर जुड़े और अप्रत्यक्ष ग्राफ़ G में कम से कम एक फैले हुए वृक्ष हैं। डिस्कनेक्ट किए गए ग्राफ़ में कोई फैले हुए पेड़ नहीं है, क्योंकि इसे अपने सभी कोने तक नहीं फैलाया जा सकता है।
हमें एक पूरे ग्राफ से तीन फैले हुए पेड़ मिले। एक पूर्ण अप्रत्यक्ष ग्राफ अधिकतम हो सकता हैnn-2 फैले पेड़ों की संख्या, जहां nनोड्स की संख्या है। उपरोक्त संबोधित उदाहरण में,n is 3, इसलिये 33−2 = 3 फैले हुए पेड़ संभव हैं।
स्पानिंग ट्री के सामान्य गुण
अब हम समझते हैं कि एक ग्राफ में एक से अधिक फैले पेड़ हो सकते हैं। ग्राफ जी से जुड़े फैले पेड़ के कुछ गुण निम्नलिखित हैं -
एक जुड़ा हुआ ग्राफ जी में एक से अधिक फैले हुए पेड़ हो सकते हैं।
ग्राफ जी के सभी संभव फैले पेड़ों में किनारों और कोने की संख्या समान है।
फैले हुए वृक्ष का कोई चक्र (लूप) नहीं होता है।
फैले पेड़ से एक किनारे को हटाने से ग्राफ काट दिया जाएगा, यानी फैले हुए पेड़ है minimally connected।
फैले हुए पेड़ में एक किनारे जोड़ने से एक सर्किट या लूप बनेगा, यानी फैले हुए पेड़ maximally acyclic।
स्पानिंग ट्री के गणितीय गुण
स्पानिंग ट्री है n-1 किनारों, जहां n नोड्स (कोने) की संख्या है।
पूर्ण ग्राफ़ से, अधिकतम हटाकर e - n + 1 किनारों, हम एक फैले हुए पेड़ का निर्माण कर सकते हैं।
एक पूरा ग्राफ अधिकतम हो सकता है nn-2 फैले पेड़ों की संख्या।
इस प्रकार, हम निष्कर्ष निकाल सकते हैं कि फैले हुए पेड़ जुड़े हुए ग्राफ जी के सबसेट हैं और डिस्कनेक्ट किए गए ग्राफ़ में फैले हुए पेड़ नहीं हैं।
स्पानिंग ट्री का अनुप्रयोग
स्पैनिंग ट्री मूल रूप से एक ग्राफ में सभी नोड्स को जोड़ने के लिए एक न्यूनतम पथ खोजने के लिए उपयोग किया जाता है। फैले पेड़ों के सामान्य अनुप्रयोग हैं -
Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis
इसे एक छोटे से उदाहरण के माध्यम से समझते हैं। विचार करें, शहर नेटवर्क को एक विशाल ग्राफ़ के रूप में और अब टेलीफोन लाइनों को इस तरह से तैनात करने की योजना है कि न्यूनतम लाइनों में हम सभी शहर नोड्स से जुड़ सकें। यह वह जगह है जहाँ फैले पेड़ चित्र में आते हैं।
न्यूनतम स्पानिंग ट्री (MST)
भारित ग्राफ़ में, एक न्यूनतम फैले हुए पेड़ एक फैले हुए पेड़ होते हैं, जिसमें एक ही ग्राफ के अन्य फैले हुए पेड़ों की तुलना में न्यूनतम वजन होता है। वास्तविक दुनिया की स्थितियों में, इस वजन को दूरी, भीड़, यातायात भार या किनारों पर निरूपित किसी भी मनमाने मूल्य के रूप में मापा जा सकता है।
न्यूनतम स्पैनिंग-ट्री एल्गोरिदम
हम यहां दो सबसे महत्वपूर्ण फैले हुए पेड़ एल्गोरिदम के बारे में जानेंगे -
क्रुस्कल का एल्गोरिदम
प्राइम का एल्गोरिथम
दोनों लालची एल्गोरिदम हैं।