Question 2Asked in Bihar STET 2025 Paper II Computer Science, 3 Nov 2025, Shift 2 (2:00 PM)

In the context of minimum spanning trees, the "cut property" is used to justify theन्यूनतम फैले हुए पेड़ों के संदर्भ में, "कट प्रॉपर्टी" का उपयोग प्राइम के एल्गोरिथ्म की शुद्धता को सही

In the context of minimum spanning trees, the "cut property" is used to justify the correctness of Prim's algorithm. What does the cut property state?

न्यूनतम फैले हुए पेड़ों के संदर्भ में, "कट प्रॉपर्टी" का उपयोग प्राइम के एल्गोरिथ्म की शुद्धता को सही ठहराने के लिए किया जाता है। कट प्रॉपर्टी स्टेट क्या है?

AThe algorithm always cuts the maximum weight edge.एल्गोरिथ्म हमेशा अधिकतम वजन बढ़त काटता है।
BThe algorithm always cuts the minimum weight edge.एल्गोरिथ्म हमेशा न्यूनतम वजन बढ़त में कटौती करता है।
CThe algorithm always cuts an edge crossing the cut with the minimum weight.एल्गोरिथ्म हमेशा न्यूनतम वजन के साथ कट को पार करते हुए एक किनारे को काटता है।
DThe algorithm always cuts an edge crossing the cut with the maximum weight.एल्गोरिथ्म हमेशा अधिकतम वजन के साथ कट को पार करते हुए एक किनारे को काटता है।

Show answerHide answer

Correct answer: (C) The algorithm always cuts an edge crossing the cut with the minimum weight.एल्गोरिथ्म हमेशा न्यूनतम वजन के साथ कट को पार करते हुए एक किनारे को काटता है।

Explanation

The cut property says that for any cut of the graph, the minimum-weight edge crossing that cut belongs to some MST. Prim's algorithm always picks the lightest edge crossing from the tree to the rest, so it is correct.Cut property कहती है कि ग्राफ़ के किसी भी cut को पार करने वाला न्यूनतम भार का एज किसी न किसी MST में होता है। Prim का एल्गोरिदम हमेशा पेड़ से बाकी की ओर जाने वाला सबसे हल्का एज चुनता है, इसलिए वह सही है।

From Bihar STET 2025 Paper II Computer Science PYQ, 3 Nov 2025, Shift 2 (2:00 PM)