6
में नया स्पैनिंग पेड़ ढूंढें मान लीजिए कि हमें दिए गए ग्राफ जी के न्यूनतम स्पैनिंग पेड़ टी (एन शिखर और एम किनारों के साथ) और एक नया एज ई = (यू, v) वजन घटाने के लिए हम जी में जोड़ देंगे ग्राफ G + e के न्यूनतम स्पैनिंग पेड़ को खोजने के लिए एक कुशल एल्गोरिदम दें। आपका एल्गोरिदम पूर्ण क्रेडिट प्राप्त करने के लिए ओ (एन) समय में चलना चाहिए।ग्राफ में नया किनारा जोड़ें और ओ (एन)
(ग) Skiena पुस्तिका से
प्रारंभ रस्मी या यू या वी से alg Kruskal जब तक हम दिया फैले पेड़ पथ का एक टुकड़ा तक पहुँचने? लगता है कि नया फैला हुआ पेड़ एक नए किनारे से बहुत कुछ नहीं बदलेगा।
इस के बाद से किया गया है एक होमवर्क बात नहीं, आप और अधिक विशेष रूप आप कोई सहायता चाहिए, क्या व्याख्या कर सकते हैं? यह एक बड़ी समस्या है, लेकिन हम आपको जवाब देने के लिए नहीं जा रहे हैं। – templatetypedef