Spanning Tree MCQ Quiz in हिन्दी - Objective Question with Answer for Spanning Tree - मुफ्त [PDF] डाउनलोड करें
Last updated on Apr 6, 2025
Latest Spanning Tree MCQ Objective Questions
Spanning Tree Question 1:
निम्नलिखित सरल ग्राफ पर विचार कीजिए।
उपरोक्त ग्राफ में संभव स्पैनिंग ट्री की संख्या ज्ञात कीजिए।
Answer (Detailed Solution Below)
Spanning Tree Question 1 Detailed Solution
सही उत्तर 8 है।
व्याख्या:
दिए गए मैट्रिक्स का आसन्नता मैट्रिक्स बनाएं।
A = \(\begin{array}{*{20}{c}} {}\\ 1\\ 2\\ 3\\ 4 \end{array}\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1&2&3&4 \end{array}}\\ {\left[ {\begin{array}{*{20}{c}} 0&1&0&1\\ 1&0&1&1\\ 0&1&0&1\\ 1&1&1&0 \end{array}} \right]} \end{array}\)
सभी 1 को -1 में परिवर्तित कीजिए और मुख्य विकर्ण में 0 को उस शीर्ष की डिग्री से बदलिए।
\(\begin{array}{*{20}{c}} {}\\ 1\\ 2\\ 3\\ 4 \end{array}\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1&2&3&4 \end{array}}\\ {\left[ {\begin{array}{*{20}{c}} 2&{ - 1}&0&{ - 1}\\ { - 1}&3&{ - 1}&{ - 1}\\ 0&{ - 1}&2&{ - 1}\\ { - 1}&{ - 1}&{ - 1}&3 \end{array}} \right]} \end{array}\)
किसी भी तत्व का सहखंड = स्पैनिंग ट्री की संख्या
स्पैनिंग ट्री की संख्या = i = 1, j = 1 पर किसी तत्व का कोफैक्टर
= 3(6 - 1) + 1(-3 - 1) - 1(1 + 2)
= 3(5) + 1(-4) - 1(3)
= 15 - 4 - 3
= 8
सबग्राफ: एक सबग्राफ एक प्रकार का ग्राफ है जिसमें इसके किनारे और शीर्ष मूल ग्राफ से सबसेट के रूप में चुने जाते हैं।
स्पैनिंग ट्री: एक स्पैनिंग ट्री एक विशिष्ट सबग्राफ है, जिसमें मूल ग्राफ के सभी शीर्ष होते हैं, और इसे एक ट्री के रूप में संरचित किया जाता है (कोई लूप नहीं बनाता है)।
Top Spanning Tree MCQ Objective Questions
Spanning Tree Question 2:
निम्नलिखित सरल ग्राफ पर विचार कीजिए।
उपरोक्त ग्राफ में संभव स्पैनिंग ट्री की संख्या ज्ञात कीजिए।
Answer (Detailed Solution Below)
Spanning Tree Question 2 Detailed Solution
सही उत्तर 8 है।
व्याख्या:
दिए गए मैट्रिक्स का आसन्नता मैट्रिक्स बनाएं।
A = \(\begin{array}{*{20}{c}} {}\\ 1\\ 2\\ 3\\ 4 \end{array}\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1&2&3&4 \end{array}}\\ {\left[ {\begin{array}{*{20}{c}} 0&1&0&1\\ 1&0&1&1\\ 0&1&0&1\\ 1&1&1&0 \end{array}} \right]} \end{array}\)
सभी 1 को -1 में परिवर्तित कीजिए और मुख्य विकर्ण में 0 को उस शीर्ष की डिग्री से बदलिए।
\(\begin{array}{*{20}{c}} {}\\ 1\\ 2\\ 3\\ 4 \end{array}\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1&2&3&4 \end{array}}\\ {\left[ {\begin{array}{*{20}{c}} 2&{ - 1}&0&{ - 1}\\ { - 1}&3&{ - 1}&{ - 1}\\ 0&{ - 1}&2&{ - 1}\\ { - 1}&{ - 1}&{ - 1}&3 \end{array}} \right]} \end{array}\)
किसी भी तत्व का सहखंड = स्पैनिंग ट्री की संख्या
स्पैनिंग ट्री की संख्या = i = 1, j = 1 पर किसी तत्व का कोफैक्टर
= 3(6 - 1) + 1(-3 - 1) - 1(1 + 2)
= 3(5) + 1(-4) - 1(3)
= 15 - 4 - 3
= 8
सबग्राफ: एक सबग्राफ एक प्रकार का ग्राफ है जिसमें इसके किनारे और शीर्ष मूल ग्राफ से सबसेट के रूप में चुने जाते हैं।
स्पैनिंग ट्री: एक स्पैनिंग ट्री एक विशिष्ट सबग्राफ है, जिसमें मूल ग्राफ के सभी शीर्ष होते हैं, और इसे एक ट्री के रूप में संरचित किया जाता है (कोई लूप नहीं बनाता है)।
Spanning Tree Question 3:
निम्नलिखित आरेख (ग्राफ) के लिए न्यूनतम विस्तृत दूरी (मिनिमम स्पानिंग डिस्टेंस) और तदनुरुपी कोरों (एजेस) की संख्या ज्ञात कीजिए:
Answer (Detailed Solution Below)
Spanning Tree Question 3 Detailed Solution
सही उत्तर: विकल्प 2 है।
Key Points
एक मिनिमम स्पानिंग ट्री (MST) ग्राफ़ में सभी शीर्षों को न्यूनतम संभव कुल किनारे भार के साथ और बिना किसी चक्र के जोड़ता है।
दिया गया है:
- शीर्षों A, B, C, D, E के साथ ग्राफ़
- किनारे भार: AB = 5, AC = 7, BD = 4, CD = 3, DE = 2, CE = 6, BC = 1
अभिगम (क्रुस्कल एल्गोरिथम का उपयोग करके):
- भार के आरोही क्रम में सभी किनारों को क्रमबद्ध करें:
- BC = 1
- DE = 2
- CD = 3
- BD = 4
- AB = 5
- CE = 6
- AC = 7
- किनारों का चयन करें जो चक्र नहीं बनाते हैं और नए नोड्स को जोड़ते हैं:
- BC = 1 (B और C को जोड़ता है)
- DE = 2 (D और E को जोड़ता है)
- CD = 3 (C और D को जोड़ता है)
- AB = 5 (A को B से जोड़ता है)
परिणाम:
- चयनित किनारे: BC, DE, CD, AB
- कुल भार = 1 + 2 + 3 + 5 = 11
- किनारों की संख्या = 4 (5 शीर्षों के लिए, MST में 5 - 1 = 4 किनारे होंगे)
सही विकल्प: विकल्प 2) 11, 4 है।