मेरे समस्या निम्नलिखित है:केंद्र नोड (दूरी भावना की एक न्यूनतम राशि में)
को देखते हुए एक पेड़ (वी, ई), केंद्र नोड वी लगता है ऐसा है कि योग {वी में w} [ dist (v, w)] न्यूनतम है, जहां dist (v, w) v से w से सबसे कम पथ में किनारों की संख्या है। एल्गोरिदम ओ (एन) समय में चलना चाहिए (एन पेड़ में नोड्स की संख्या होने के नाते)।
प्रश्न here और here भी केंद्र नोड के लिए पूछते हैं लेकिन इसे अलग-अलग परिभाषित करते हैं।
मैंने कठोर कदमों से गुजरना नहीं है लेकिन मुझे वास्तव में लगता है कि मेरी समस्या का समाधान this problem के समाधान के समान होना चाहिए।
हालांकि, मैंने फैसला किया कि मुझे अपनी समस्या को समुदाय के साथ साझा करना चाहिए क्योंकि मुझे the link पर नेविगेट करने में कुछ समय लगा, हालांकि यह सीधे सवाल का जवाब नहीं देता है।
@maraca - मुझे लगता है कि आप जो कह रहे हैं वह थोड़ा गलत हो सकता है। ऐसे मामले के बारे में सोचें जहां परिणामी पेड़ की ऊंचाई एक पेड़ से एक और है जो आपको _one_ शाखा के कारण मिलती है, लेकिन दूरी की कुल राशि कम होती है। मुझे पूरी तरह से यकीन नहीं है कि यह काउंटर उदाहरण वास्तव में अस्तित्व में हो सकता है, मैं केवल यह सुझाव दे रहा हूं कि इसकी जांच की जानी चाहिए ... –
@maraca हां, मैं एक इष्टतम रूट खोजना चाहता हूं। मेरे पास इसके बारे में है और मैं आपको एक काउंटर-उदाहरण दे सकता हूं जहां समाधान समान नहीं हैं। एक पेड़ की कल्पना करें जहां रूट में कई पड़ोसियों हैं, एम कहें, जिनमें से प्रत्येक छुट्टी है, और लंबाई की एक 'पूंछ' 3 कहती है (जिसमें 3 शिखर होते हैं)। फिर सबसे कम गहराई से खोजा गया रूट वर्टेक्स कई पड़ोसियों के साथ नहीं होगा (यह पूंछ पर पहला चरम होगा, जो हर दूसरे कशेरुक के लिए न्यूनतम दूरी 2 का परिणाम देगा), और मेरी समस्या का समाधान एक होगा कई पड़ोसियों के साथ। – MindaugasK
@MindaugasK मेरी गलती क्षमा करें, आप रूट के लिए रकम की दूरी को कम करना चाहते हैं और सभी नोड्स के बीच नहीं ... – maraca