एन नोड्स के बीच के लिंक का उपयोग करके कुल दूरी को कम करें

Question

मैं निम्नलिखित समस्या के साथ आया कि मुझे समाधान की जानकारी नहीं है और न ही मुझे आगे की जांच करने के लिए 'लुकअप' शब्द मिल सकता है।

कहें कि हमारे पास एन ने आदेश दिया है कि नोड्स (n_1, n_2 .... n_N) प्रत्येक के बीच 1 की निश्चित दूरी के साथ। तो dist (n_1, n_N) = N-1। अब हमें किसी भी दो नोड्स को जोड़ने की इजाजत है, इस प्रकार प्रभावी रूप से उनकी दूरी को कम करने के लिए 1. मान लें कि हमारे पास ऐसे कनेक्शन हो सकते हैं।

समस्या यह है कि हम कैसे चुनते हैं कि कौन से नोड्स किसी भी दो नोड्स के बीच कुल दूरी को कम करने के लिए कनेक्ट करते हैं?

क्या यह समस्या कुछ अच्छी तरह से अध्ययन की गई समस्या का ज्ञात संस्करण है? एक कुशल समाधान इस के लिए मौजूद है (या एक संस्करण है, जहां हम केवल किसी भी दो नोड्स के बीच अधिकतम दूरी को कम करना चाहते हैं)

धन्यवाद

Answer 1

आप "On the sum of all distances in a graph or digraph" में रुचि हो सकती। वह पेपर आपके "कुल दूरी" को ग्राफ के "ट्रांसमिशन" के रूप में संदर्भित करता है। आपकी "अधिकतम दूरी" को आमतौर पर ग्राफ के "व्यास" कहा जाता है। यह दोनों पर चर्चा करता है, ग्राफ के संचरण के कुछ गुण साबित करता है, और दिखाता है कि संचरण और व्यास एक दूसरे से स्वतंत्र हैं।

Naively, आपको कोशिश करने के लिए n-select-k विकल्प मिल गए हैं। अगर एन और के बड़े हैं तो यह बहुत बुरा है। उनमें से कोई छोटा नहीं है तो बहुत बुरा नहीं है।

इससे बेहतर करने पर काम है। This Mathoverflow question शिखर के बीच औसत दूरी को कम करने के बारे में पूछता है, जो ग्राफ के संचरण के समान है। दो जवाब हैं, जिनमें से कोई भी मैं झुक सकता हूं। यह a paper को भी संदर्भित करता है जो सीधे इस प्रश्न को संबोधित करता है।

ग्राफ़ के व्यास को कम करने के लिए this paper में निपटाया जाता है।

आप इस प्रश्न को मैथ स्टैक एक्सचेंज में संबोधित करने पर विचार कर सकते हैं।