Question
Download Solution PDFक्रुस्कल के एल्गोरिथम का उपयोग करके गणना किए गए ग्राफ G में न्यूनतम स्पैनिंग ट्री का वजन ____ है।
Answer (Detailed Solution Below)
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
Last updated on Jun 12, 2025
-> The UGC NET June 2025 exam will be conducted from 25th to 29th June 2025.
-> The UGC-NET exam takes place for 85 subjects, to determine the eligibility for 'Junior Research Fellowship’ and ‘Assistant Professor’ posts, as well as for PhD. admissions.
-> The exam is conducted bi-annually - in June and December cycles.
-> The exam comprises two papers - Paper I and Paper II. Paper I consists of 50 questions and Paper II consists of 100 questions.
-> The candidates who are preparing for the exam can check the UGC NET Previous Year Papers and UGC NET Test Series to boost their preparations.