ग्राफ सिद्धांत में, एक पेड़ है एक अप्रत्यक्ष ग्राफ जिसमें कोई भी दो कोने बिल्कुल एक पथ से जुड़े होते हैं, या समकक्ष रूप से एक जुड़ा हुआ चक्रीय अप्रत्यक्ष ग्राफ। … एक पॉलीफ़ॉरेस्ट (या निर्देशित फ़ॉरेस्ट या ओरिएंटेड फ़ॉरेस्ट) एक निर्देशित एसाइक्लिक ग्राफ है जिसका अंतर्निहित अप्रत्यक्ष ग्राफ एक जंगल है।
निर्देशित और अप्रत्यक्ष पेड़ क्या हैं?
बिना चक्र वाला एक अप्रत्यक्ष ग्राफ जंगल है और अगर इसे जोड़ा जाए तो इसे पेड़ कहा जाता है। एक निर्देशित ग्राफ एक जंगल (या पेड़) होता है यदि सभी किनारों को अप्रत्यक्ष किनारों में परिवर्तित किया जाता है तो यह अप्रत्यक्ष वन (या पेड़) होता है। जड़ वाला पेड़ एक ऐसा पेड़ होता है जिसका एक शीर्ष जड़ के रूप में निर्दिष्ट होता है।
पेड़ अप्रत्यक्ष क्यों होते हैं?
प्रमेय: एक अप्रत्यक्ष ग्राफ एक पेड़ है यदि प्रत्येक जोड़ी के बीच एक सरल पथ हैप्रमाण: यदि हमारे पास एक ग्राफ T है जो एक पेड़ है, तो इसे बिना किसी चक्र के जोड़ा जाना चाहिए। चूंकि T जुड़ा हुआ है, इसलिए प्रत्येक जोड़े के बीच कम से कम एक सरल पथ होना चाहिए।
निर्देशित वृक्ष का क्या अर्थ है?
एक निर्देशित पेड़ है एक चक्रीय निर्देशित ग्राफ इसमें एक नोड के साथ डिग्री 1 है, जबकि अन्य सभी नोड्स में डिग्री 1 है जैसा कि अंजीर में दिखाया गया है: नोड जिसमें आउटडिग्री 0 है बाहरी नोड या टर्मिनल नोड या लीफ कहा जाता है। जिन नोड्स की डिग्री एक से अधिक या उसके बराबर होती है, उन्हें आंतरिक नोड कहा जाता है।
आप कैसे बताते हैं कि एक अप्रत्यक्ष ग्राफ एक पेड़ है?
अप्रत्यक्ष ग्राफ़ के मामले में, हम तीन चरणों का पालन करते हैं:
- यह सुनिश्चित करने के लिए कि प्रत्येक नोड में ठीक एक पैरेंट है, किसी भी नोड से DFS जाँच करें। यदि नहीं, तो वापस लौटें।
- जांचें कि सभी नोड्स का दौरा किया गया है। यदि DFS चेक सभी नोड्स पर नहीं जा पा रहा था, तो वापस लौटें।
- अन्यथा, ग्राफ एक पेड़ है।
