Graphs/Spanning Tree and Shortest Paths MCQ Quiz in हिन्दी - Objective Question with Answer for Graphs/Spanning Tree and Shortest Paths - मुफ्त [PDF] डाउनलोड करें
Last updated on Jul 16, 2025
Latest Graphs/Spanning Tree and Shortest Paths MCQ Objective Questions
Graphs/Spanning Tree and Shortest Paths Question 1:
क्रुस्कल के एल्गोरिथम का उपयोग करके गणना किए गए ग्राफ G में न्यूनतम स्पैनिंग ट्री का वजन ____ है।
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 1 Detailed Solution
संकल्पना:
एक न्यूनतम स्पैनिंग ट्री (MST) या न्यूनतम वजन स्पैनिंग ट्री एक जुड़े, किनारे-भारित अप्रत्यक्ष ग्राफ G(V, E) के किनारों (V – 1 ) का एक सबसेट है जो सभी शिखरों को एक साथ जोड़ता है, बिना किसी चक्र के और न्यूनतम संभव कुल किनारे वजन के साथ।
व्याख्या:
दिए गए ग्राफ के लिए किनारा सेट = {2, 3, 4, 5, 6, 7, 8}
5 कोने के लिए, हमें MST में 4 किनारों की आवश्यकता है,
तो, MST के लिए किनारा सेट = {2, 3, 4, 6}
न्यूनतम स्पैनिंग ट्री
न्यूनतम लागत 2 + 3 + 4 + 6 = 15
Graphs/Spanning Tree and Shortest Paths Question 2:
कौन-सा पथक्रमण एल्गोरिदम आमतौर पर स्टैक डेटा संरचना का उपयोग करके कार्यान्वित किया जाता है?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 2 Detailed Solution
सही उत्तर DFS है।
Key Points
- गहराई-प्रथम खोज आमतौर पर स्टैक डेटा संरचना का उपयोग करके कार्यान्वित की जाती है। एल्गोरिथम बैकट्रैकिंग से पहले प्रत्येक शाखा के साथ यथासंभव अन्वेषण करता है। स्टैक विज़िट किए जाने वाले शीर्षों पर नज़र रखने में मदद करता है, जिससे एल्गोरिदम को कुशलतापूर्वक पीछे जाने की अनुमति मिलती है।
- चौड़ाई-प्रथम खोज (BFS) आमतौर पर कतार डेटा संरचना का उपयोग करके कार्यान्वित की जाती है।
Graphs/Spanning Tree and Shortest Paths Question 3:
निम्न में से कौन-सा एक ग्राफ को ब्रेड्थ फर्स्ट सर्च (BPS) द्वारा ट्रैवर्स करने में उपयोगी है?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 3 Detailed Solution
The correct answer is Queue
Key Points
- Queue: ✅ A queue is used in Breadth-First Search (BFS) to keep track of nodes to be explored. BFS explores all nodes at the current depth level before moving to nodes at the next depth level. This behavior matches the First-In-First-Out (FIFO) nature of a queue.
- Stack: ❌ A stack is used in Depth-First Search (DFS) because it follows a Last-In-First-Out (LIFO) approach, which is suitable for exploring deeper nodes before backtracking.
- Set: ❌ While a set can be used to track visited nodes, it is not suitable for traversal itself as it does not maintain order.
- List: ❌ A list is a general data structure that can store elements, but it does not inherently provide the FIFO behavior needed for BFS.
Additional Information
- How BFS Works: BFS starts at a given node and explores all its neighbors before moving on to the neighbors of those nodes. This ensures that nodes are visited layer by layer.
- Applications: BFS is used in finding shortest paths in unweighted graphs, solving puzzles like mazes, and in network broadcasting.
- Queue Implementation: A queue is implemented by adding nodes to the rear and removing nodes from the front to ensure FIFO behavior.
Graphs/Spanning Tree and Shortest Paths Question 4:
निम्न में से कौन सा ऐल्गोरिद्म ऑल-पेयर्स शॉर्टस्ट पाथ प्रॉब्लम को हल कर सकता है?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 4 Detailed Solution
The correct answer is Floyd's algorithm
Key Points
- Dijkstra's Algorithm: ❌ Dijkstra's algorithm is primarily used to find the shortest path from a single source to all vertices in a graph. It does not solve the all-pairs shortest path problem.
- Floyd's Algorithm: ✅ Floyd-Warshall algorithm is specifically designed to solve the all-pairs shortest path problem. It works by iteratively improving the shortest paths between all pairs of vertices using a dynamic programming approach.
- Prim's Algorithm: ❌ Prim's algorithm is used for finding the Minimum Spanning Tree (MST) of a graph, not for solving shortest path problems.
- Warshall's Algorithm: ❌ Warshall's algorithm is used for transitive closure of a graph, not for solving the all-pairs shortest path problem.
Additional Information
- The Floyd-Warshall algorithm is a dynamic programming algorithm that compares all possible paths between every pair of vertices in a weighted graph to find the shortest paths.
- It has a time complexity of O(V³), where V is the number of vertices in the graph.
- This algorithm works for both directed and undirected graphs, as long as there are no negative weight cycles in the graph.
- The main advantage of Floyd-Warshall is its simplicity and ability to handle dense graphs efficiently.
Graphs/Spanning Tree and Shortest Paths Question 5:
निम्नलिखित में से कौन ग्राफ ट्रैवर्सल एल्गोरिथम नहीं है ?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 5 Detailed Solution
सही उत्तर उपरोक्त में से एक से अधिक है।
Key Points
- ग्रीडी: यह एक प्रकार का एल्गोरिथम प्रतिमान है जो एक समाधान को टुकड़े-टुकड़े करके बनाता है, हमेशा अगला टुकड़ा चुनता है जो सबसे तत्काल लाभ प्रदान करता है। जबकि इसे ग्राफ से संबंधित समस्याओं (जैसे न्यूनतम स्पेनिंग ट्री योजना) पर लागू किया जा सकता है, यह स्वयं एक ग्राफ ट्रैवर्सल एल्गोरिथम नहीं है।
- विभाजन और विजय: यह एक और एल्गोरिथम पैराडाइम है जो एक समस्या को छोटी उप-समस्याओं में विभाजित करता है, प्रत्येक उप-समस्या को स्वतंत्र रूप से हल करता है, और उनके समाधानों को जोड़ता है। यह विशेष रूप से एक ग्राफ ट्रैवर्सल एल्गोरिथम नहीं है।
- गतिक प्रोग्रामन: यह तकनीक समस्याओं को सरल उप-समस्याओं में तोड़कर हल करती है और इन उप-समस्याओं के परिणामों को संग्रहीत करती है ताकि अनावश्यक गणनाओं से बचा जा सके। दूसरों की तरह, यह एक ग्राफ ट्रैवर्सल एल्गोरिथम नहीं है, लेकिन इसे ग्राफ से संबंधित समस्याओं पर लागू किया जा सकता है।
निष्कर्ष:
- चूँकि सूचीबद्ध विकल्पों में से कोई भी (ग्रीडी, विभाजन और कॉक्वेर और गतिक प्रोग्रामन) ग्राफ ट्रैवर्सल एल्गोरिथम (जैसे गहराई-प्रथम खोज (DFS) या चौड़ाई-प्रथम खोज (BFS)) नहीं है, इसलिए उत्तर 4) उपरोक्त में से एक से अधिक है।
Top Graphs/Spanning Tree and Shortest Paths MCQ Objective Questions
डेप्थ फर्स्ट सर्च ग्राफ सर्च एल्गोरिथम इसके कार्यान्वयन के लिए _______ डेटा संरचना का उपयोग करता है।
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 6 Detailed Solution
Download Solution PDF- ब्रेड्थ-फर्स्ट सर्च (BFS) और डेप्थ फर्स्ट सर्च (DFS) ट्री या ग्राफ डेटा संरचनाओं को पार करने या खोजने के लिए एक एल्गोरिदम है।
- डेप्थ फर्स्ट सर्च (DFS) स्टैक डेटा संरचना का उपयोग करता है। DFS बैकट्रैकिंग तकनीक का उपयोग करता है। याद रखें कि स्टैक द्वारा बैकट्रैकिंग आगे बढ़ सकती है।
- ब्रेड्थ-फर्स्ट सर्च (BFS) एल्गोरिथम एक ग्राफ़ को चौड़ाई के हिसाब से ट्रेस करता है और किसी भी पुनरावृत्ति में एक अंतिम छोर होने पर खोज शुरू करने के लिए अगला शीर्ष प्राप्त करने के लिए याद रखने के लिए एक कतार का उपयोग करता है।
पंक्ति संरचना का उपयोग _______ में किया जाता है।
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 7 Detailed Solution
Download Solution PDF- चौड़ाई-प्रथम खोज (BFS) और गहराई प्रथम खोज (DFS) ट्री या ग्राफ डेटा संरचनाओं को चंक्रमण या खोजने के लिए एक एल्गोरिथ्म है।
- चौड़ाई प्रथम खोज (BFS) एल्गोरिथ्म चंक्रमण एक ग्राफ को चौड़ाई में बदल देता है और खोज शुरू करने के लिए अगला शीर्ष प्राप्त करने के लिए याद रखने के लिए एक पंक्ति का उपयोग करता है, जब किसी भी पुनरावृत्ति में एक आखिरी अंत होता है।
- गहराई प्रथम खोज (DFS) स्टैक डेटा संरचना का उपयोग करती है। DFS बैकट्रैकिंग तकनीक का उपयोग करता है। याद रखें बैकट्रैक स्टैक द्वारा आगे बढ़ सकता है।
क्रुस्कल के एल्गोरिथम का उपयोग करके गणना किए गए ग्राफ G में न्यूनतम स्पैनिंग ट्री का वजन ____ है।
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 8 Detailed Solution
Download Solution PDFसंकल्पना:
एक न्यूनतम स्पैनिंग ट्री (MST) या न्यूनतम वजन स्पैनिंग ट्री एक जुड़े, किनारे-भारित अप्रत्यक्ष ग्राफ G(V, E) के किनारों (V – 1 ) का एक सबसेट है जो सभी शिखरों को एक साथ जोड़ता है, बिना किसी चक्र के और न्यूनतम संभव कुल किनारे वजन के साथ।
व्याख्या:
दिए गए ग्राफ के लिए किनारा सेट = {2, 3, 4, 5, 6, 7, 8}
5 कोने के लिए, हमें MST में 4 किनारों की आवश्यकता है,
तो, MST के लिए किनारा सेट = {2, 3, 4, 6}
न्यूनतम स्पैनिंग ट्री
न्यूनतम लागत 2 + 3 + 4 + 6 = 15
माना G = (V, E) कोई भी जुड़ा हुआ अप्रत्यक्ष किनारा-भारित ग्राफ है। E में किनारों का भार धनात्मक और विशिष्ट है। निम्नलिखित कथनों पर विचार करें:
I) G का न्यूनतम विस्तारित ट्री हमेशा अद्वितीय होता है।
II) G के किन्हीं दो शीर्षों के बीच सबसे छोटा पथ सदैव अद्वितीय होता है।
उपरोक्त में से कौन सा/से कथन अनिवार्य रूप से सत्य है/हैं?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 9 Detailed Solution
Download Solution PDFसंकल्पना:
एक न्यूनतम विस्तारित ट्री (MST) या न्यूनतम भार वाला विस्तारित ट्री संयोजित भारित अप्रत्यक्ष ग्राफ G(V, E) के किनारों का उपवर्ग (V – 1 ) है जो न्यूनतम संभव कुल कोर के साथ बिना किसी चक्र के सभी शीर्षों को एक साथ जोड़ता है।
उदाहरण:
ग्राफ G(V, E)
G(V, V – 1) → न्यूनतम विस्तारित ट्री
यदि किनारे के वजन अलग हैं तो अद्वितीय MST मौजूद है।
अतः कथन I सत्य है।
जब किनारे के भार अलग और धनात्मक होते हैं तो उस स्थिति में ग्राफ के किन्हीं दो शीर्षों के बीच का सबसे छोटा पथ हमेशा अद्वितीय नहीं होता है। सबसे छोटा रास्ता अलग हो सकता है, भले ही किनारे के वजन अद्वितीय हों।
उदाहरण:
A → C (3) और A → B → C (1 + 2 = 3) के बीच की दूरी, दोनों रास्तों की दूरी समान है।
इसलिए कथन II असत्य है।
मान लीजिए G एक प्रत्यक्ष ग्राफ है जिसका शीर्ष समुच्चय 1 से 100 तक की संख्याओं का समुच्चय है। एक शीर्ष i से एक शीर्ष j तक एक एज है यदि और केवल यदि या तो j = i + 1 या j = 3i है। शीर्ष 1 से शीर्ष 100 तक G में पथ में एज की न्यूनतम संख्या _______ है।
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 10 Detailed Solution
Download Solution PDFसही उत्तर विकल्प 4 है।
Key Points
एज सेट में i से j तक एज होते हैं, या तो दो स्थितियों का उपयोग करते हुए j = i + 1 या j = 3i दूसरी पसंद हमें 1 से 100 तक जाने में मदद करती है। इसे स्लॉट करने की ट्रिक दूसरी तरफ सोचना है। 100 से 1 निशान होने के बजाय 100 से 1 निशान खोजने का प्रयास करें।
तो, एज की न्यूनतम संख्या के साथ एज का क्रम है
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100
जिसमें 7 एज होते हैं।
अतः सही उत्तर 7 है।
नीचे दिए गए निदेशित ग्राफ पर विचार करें।
निम्नलिखित में से कौन सा सत्य (TRUE) है?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 11 Detailed Solution
Download Solution PDFसंकल्पना:
इस ग्राफ का कोई चक्र नहीं है, इसलिए एक सांस्थितिक क्रम (टोपोलॉजिकल ऑर्डरिंग) मौजूद होना चाहिए।
R के पास P और S से एक इनडिग्री है। Q के पास P, R और S से इनडिग्री है। इसलिए,
- P और S को सांस्थितिक क्रम में R में प्रकट होना चाहिए।
- P, S, R को सांस्थितिक क्रम में Q से पहले उपस्थित होना चाहिए।
- P और S के अनुक्रम में कोई डिग्री नहीं है जिसे आपस में बदला जा सकता है।
इस प्रकार, मान्य सांस्थितिक क्रम PSRQ और SPRQ हैं।
स्पष्टीकरण:
सांस्थितिक क्रम के लिए, शुरुआती शीर्ष में 0 इनडिग्री होनी चाहिए। इसलिए, P या S में से किसी एक को चुना जा सकता है।
यदि हम P चुनते हैं, तो हमें केवल P से इनडिग्री के साथ अगला शीर्ष चुनना होगा। इसलिए, S को चुना जाता है।
P और S के बाद, हम केवल P और S से इनडिग्री के साथ एक शीर्ष चुनते हैं। इसलिए R के बाद Q।
P के बजाय S के साथ भी ऐसा निष्पादन किया जा सकता है।
सात शीर्षों वाले एक पूर्ण ग्राफ के लिए स्पैनिंग ट्री की संख्या क्या है?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 12 Detailed Solution
Download Solution PDFसंकल्पना:
एक स्पैनिंग ट्री ग्राफ G का एक उपसमुच्चय है, जिसमें सभी किनारे न्यूनतम संभव किनारों से ढके होते हैं। स्पैनिंग ट्री में चक्र नहीं होते हैं और इसे असंयोजित नहीं किया जा सकता है।
सूत्र:
n नोड्स के साथ संभव स्पैनिंग ट्री की संख्या = nn-2
गणना:
यहाँ शीर्षों की संख्या 7 है।
इसलिए, स्पैनिंग ट्री की संभव संख्या = 77-2 = 75 है
मान लीजिए G एक ग्राफ है जिसमें n शीर्ष और m किनारे हैं। G पर डेप्थ फर्स्ट सर्च के रनिंग टाइम पर सबसे टाइट उपरी परिबद्ध क्या है, जब G को आसन्न मैट्रिक्स के रूप में दर्शाया जाता है?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 13 Detailed Solution
Download Solution PDFसंकल्पना
आसन्न मैट्रिक्स प्रतिनिधित्व में, ग्राफ को "n x n”" मैट्रिक्स के रूप में दर्शाया जाता है।
ग्राफ:
फिर, इसकी आसन्नता मैट्रिक्स होगी
व्याख्या:
उपरोक्त ग्राफ या ग्राफ G के किसी भी आसन्न मैट्रिक्स पर DFS प्रदर्शित करने के लिए, हम उस शीर्ष के अनुरूप पंक्ति को पार करते हैं। इस तरह, हम सभी आसन्न शीर्ष पाते हैं।
इसलिए, G पर डेप्थ फर्स्ट सर्च के रनिंग टाइम पर सबसे ऊपरी परिबद्ध, जब G को आसन्न मैट्रिक्स के रूप में दर्शाया जाता है, Θ (n2) है।
ब्रेथ फर्स्ट सर्च (BFS) एल्गोरिथम को क्यू डेटा संरचना का उपयोग करके लागू किया गया है। निम्नलिखित में से कौन सा नीचे दिए गए ग्राफ़ में नोड्स पर जाने का संभावित क्रम है?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 14 Detailed Solution
Download Solution PDFसंकल्पना:
ब्रेथ फर्स्ट सर्च में एक बार में एक स्तर पर एक ट्री के माध्यम से सर्च शामिल है। ग्रैंडचिल्ड्रेन नोड्स के माध्यम से पार करने के लिए, पहले चाइल्ड नोड के एक पूरे स्तर के माध्यम से ट्रैवर्स करें।
व्याख्या:
1) MNOPQR
इसमें, ट्रैवर्सल S से शुरू होता है लेकिन M के चाइल्ड नोड N और Q से पहले O का ट्रैवर्सल किया जाता है। तो, गलत है।
2) NQMPOR
यह भी गलत है, P को O से पहले ट्रैवर्स किया जाता है।
3) QMNROP
गलत है, क्योंकि O को R से पहले ट्रैवर्स किया जाना चाहिए।
तो, विकल्प 4) सही है।
मान लीजिए G एक भारित संयोजित अप्रत्यक्ष ग्राफ है जिसमें भिन्न धनात्मक किनारे भार हैं। यदि प्रत्येक किनारे के भार को समान मान से बढ़ाया जाता है, तो निम्नलिखित में से कौन सा कथन सत्य है?
P: G का न्यूनतम वितान तरु (स्पैनिंग ट्री) परिवर्तित नहीं होता है
Q: किसी भी शीर्ष युग्मों के बीच सबसे छोटा पथ परिवर्तित नहीं हो सकता है
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 15 Detailed Solution
Download Solution PDFसंकल्पना:
एक न्यूनतम वितान तरु (MST) या न्यूनतम भार वाला वितान तरु संयोजित भारित अप्रत्यक्ष ग्राफ G(V, E) के किनारों का उपवर्ग (V – 1 ) है जो न्यूनतम संभव कुल कोर के साथ बिना किसी चक्र के सभी शीर्षों को एक साथ जोड़ता है।
उदाहरण:
ग्राफ G(V, E)
A और C के बीच लघुतम पथ = A → B और B → C, अर्थात्,1 + 2 = 3
G(V, V – 1) → न्यूनतम वितान तरु (स्पैनिंग ट्री)
G(V, E) का भार 10 से बढाऐं
ग्राफ G'(V, E)
A और C के बीच लघुतम पथ = A → C = 20 (विभिन्न पथ)
G'(V, V – 1) →न्यूनतम वितान तरु (स्पैनिंग ट्री)
कथन P: सत्य
G का न्यूनतम वितान तरु (स्पैनिंग ट्री) परिवर्तित नहीं होता है।
कथन Q: गलत
किसी भी शीर्ष युग्म के बीच सबसे छोटा पथ परिवर्तित नहीं हो सकता है।