वृक्ष और स्पैनिंग संरचनाएँ
एक वृक्ष एक जुड़ा हुआ अचक्रीय ग्राफ होता है, और स्पैनिंग संरचनाएँ बड़े ग्राफों से ऐसे न्यूनतम जुड़े हुए कंकाल निकालती हैं।
Definition
एक वृक्ष बिना चक्रों वाला एक जुड़ा हुआ ग्राफ होता है; एक जुड़े हुए ग्राफ का एक स्पैनिंग वृक्ष एक सबग्राफ होता है जो एक वृक्ष होता है और ग्राफ के प्रत्येक शीर्ष को शामिल करता है।
Scope
यह विषय वृक्षों के समतुल्य लक्षण वर्णन, रूटेड और लेबल किए गए वृक्षों, स्पैनिंग वृक्षों और वनों, और कैली के सूत्र और मैट्रिक्स-ट्री प्रमेय के माध्यम से उनकी गणना को शामिल करता है। यह न्यूनतम स्पैनिंग वृक्षों को एक अनुकूलन समस्या के रूप में भी प्रस्तुत करता है, जो ग्राफ सिद्धांत को एल्गोरिथम डिज़ाइन और संयोजनात्मक गणना से जोड़ता है।
Core questions
- एक ग्राफ को वृक्ष के रूप में कौन सी समतुल्य स्थितियाँ दर्शाती हैं?
- दिए गए शीर्षों की संख्या पर कितने लेबल किए गए वृक्ष होते हैं?
- एक दिया गया ग्राफ कितने स्पैनिंग वृक्षों को समाहित करता है?
- न्यूनतम कुल भार वाले स्पैनिंग वृक्ष को कुशलतापूर्वक कैसे खोजा जा सकता है?
Key concepts
- अचक्रीय जुड़े हुए ग्राफ
- रूटेड और लेबल किए गए वृक्ष
- स्पैनिंग वृक्ष और वन
- प्रूफर अनुक्रम
- कैली का सूत्र
- न्यूनतम स्पैनिंग वृक्ष
Key theories
- कैली का सूत्र
- n शीर्षों पर ठीक n^(n-2) विशिष्ट लेबल किए गए वृक्ष होते हैं, जो एक शास्त्रीय गणना परिणाम है जिसे प्रूफर अनुक्रमों, मैट्रिक्स-ट्री प्रमेय, या कई सुरुचिपूर्ण द्विपक्षीयताओं द्वारा सिद्ध किया जा सकता है।
- मैट्रिक्स-ट्री प्रमेय
- एक ग्राफ के स्पैनिंग वृक्षों की संख्या उसके लाप्लासियन मैट्रिक्स के किसी भी सहकारक के बराबर होती है, जो स्पैनिंग वृक्षों की संयोजनात्मक गणना को रैखिक बीजगणित और निर्धारकों से जोड़ता है।
Clinical relevance
स्पैनिंग वृक्ष नेटवर्क डिज़ाइन और ब्रॉडकास्ट रूटिंग के आधार हैं, न्यूनतम स्पैनिंग वृक्ष सबसे कम लागत वाली कनेक्शन समस्याओं को हल करते हैं, और वृक्ष संरचनाएँ कंप्यूटर विज्ञान में डेटा और पदानुक्रमों को व्यवस्थित करती हैं।
History
किरचॉफ के 19वीं सदी के विद्युत नेटवर्क के अध्ययन ने मैट्रिक्स-ट्री प्रमेय का निर्माण किया, जबकि कैली की 1889 की लेबल किए गए वृक्षों की गणना गणनात्मक ग्राफ सिद्धांत में सबसे प्रसिद्ध सूत्रों में से एक बन गई।
Key figures
- Arthur Cayley
- Gustav Kirchhoff
- Heinz Prufer
Related topics
Seminal works
- diestel2017
- stanley2011
Frequently asked questions
- n शीर्षों वाले वृक्ष में ठीक n-1 किनारे क्यों होते हैं?
- एक वृक्ष जुड़ा हुआ होता है, जो कम से कम n-1 किनारों को मजबूर करता है, और अचक्रीय होता है, जो अधिक को प्रतिबंधित करता है; दोनों स्थितियाँ मिलकर किनारों की संख्या को ठीक n-1 पर निर्धारित करती हैं।
- स्पैनिंग वृक्ष का उपयोग किस लिए किया जाता है?
- एक स्पैनिंग वृक्ष नेटवर्क को जोड़े रखने वाले कनेक्शनों का एक न्यूनतम सेट प्रदान करता है, जो कुशल प्रसारण और सबसे कम लागत वाले नेटवर्क डिज़ाइन का आधार है।