दूरी (ग्राफ सिद्धांत)

आरेख सिद्धांत के गणितीय क्षेत्र में आरेख़ में दो शीर्षों के बीच की दूरी उन्हें संबद्ध करने वाले सबसे छोटे पथ (जिसे आरेख़ जियोडेसिक भी कहा जाता है) में शीर्षों की संख्या होती है। इसे जियोडेसिक दूरी या सबसे छोटी पथ दूरी के रूप में भी जाना जाता है। ध्यान दें कि दो शीर्षों के बीच एक से अधिक लघुतम पथ हो सकते हैं। यदि दो शीर्षों को जोड़ने वाला कोई पथ नहीं है, अर्थात यदि वे विभिन्न संबद्ध घटकों से संबंधित हैं, तो पारंपरिक रूप से दूरी को अपरिमित के रूप में परिभाषित किया जाता है।

एक निर्देशित आरेख की स्थिति में दूरी d(u,v) दो शीर्षों u और v के बीच की दूरी को u से v तक सबसे छोटे निर्देशित पथ की लंबाई के रूप में परिभाषित किया गया है, जिसमें कम से कम एक पथ सम्मिलित होता है। ध्यान दें कि, अप्रत्यक्ष रेखांकन की स्थिति के विपरीत d(u,v) आवश्यक नहीं कि d(v,u) के साथ अनुरूप है यह सिर्फ एक अर्ध-आव्यूह है और यह स्थिति हो सकती है कि एक को परिभाषित किया गया है जबकि दूसरे को परिभाषित नही किया गया है।

संबंधित अवधारणाएं

समुच्चय पर परिभाषित आरेख़ में दूरियों के संदर्भ में बिंदुओं के एक समुच्चय पर परिभाषित एक आव्यूह समष्टि को आरेख़ आव्यूह कहा जाता है। शीर्ष समुच्चय (एक अप्रत्यक्ष आरेख़ का) और दूरी फलन एक आव्यूह समष्टि बनाते हैं यदि और केवल यदि आरेख़ संबद्ध है।

किसी शीर्ष v की उत्केन्द्रता ϵ(v) और v किसी अन्य शीर्ष के बीच की अधिकतम दूरी होती है तब प्रतीकों में,

$\epsilon (v)=\max _{u\in V}d(v,u).$

यह सोचा जा सकता है कि आरेख़ में नोड से सबसे दूर नोड से कितनी दूर है।

आरेख़ की त्रिज्या r किसी भी शीर्ष की न्यूनतम विकेन्द्रता है या प्रतीकों में,

$r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u).$

किसी आरेख़ का व्यास d आरेख़ में किसी भी शीर्ष की अधिकतम उत्केन्द्रता है। अर्थात्, d शीर्षों के किसी भी युग्म के बीच की सबसे बड़ी दूरी है या वैकल्पिक रूप से,

$d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u).$

किसी आरेख़ का व्यास ज्ञात करने के लिए, पहले प्रत्येक युग्म के शीर्षों के बीच सबसे छोटा पथ ज्ञात करें। इनमें से किसी भी पथ की सबसे बड़ी लंबाई आरेख़ का व्यास है। त्रिज्या r के एक आरेख में एक केंद्रीय शीर्ष वह है जिसका उत्केन्द्रता r है अर्थात, एक शीर्ष जिसकी दूरी उसके सबसे दूर के शीर्ष से त्रिज्या के समकक्ष के बराबर है एक शीर्ष v जैसे कि ϵ(v) = r व्यास d के आरेख़ में एक परिधीय शीर्ष वह है जिसकी उत्केन्द्रता d है अर्थात्, एक शीर्ष जिसकी दूरतम शीर्ष से दूरी व्यास के बराबर है। औपचारिक रूप से, v परिधीय है यदि ϵ(v) = d छद्म-परिधीय शीर्ष v में यह गुण होता है कि, किसी भी शीर्ष u के लिए, यदि u यथासंभव v से दूर है, तो v यथासंभव दूर है। औपचारिक रूप से, एक शीर्ष v छद्म-परिधीय होता है यदि प्रत्येक शीर्ष u के लिए d(u,v) = ϵ(v) के साथ, यह मानता है कि ϵ(u) = ϵ(v) आरेख़ की एक स्तर संरचना, एक प्रारंभिक शीर्ष दिया गया है प्रारंभिक शीर्ष से उनकी दूरी के आधार पर आरेख़ के शीर्ष का उप समुच्चय में विभाजन है।

एक जियोडेटिक आरेख वह होता है जिसके लिए प्रत्येक जोड़े के शीर्ष में उन्हें जोड़ने वाला एक अन्य सबसे छोटा पथ होता है। उदाहरण के लिए, सभी पेड़ जियोडेटिक होते हैं।

भारित सबसे छोटी-पथ दूरी, भारित आरेख़ के लिए जियोडेसिक दूरी का सामान्यीकरण करता है। इस स्थिति में यह माना जाता है कि शीर्ष का भार इसकी लंबाई का प्रतिनिधित्व करता है या जटिल नेटवर्क के लिए परस्पर क्रिया की लागत और भारित सबसे छोटी-पथ दूरी d^W(u, v) को संबद्ध करने वाले सभी पथों में भार का न्यूनतम योग है तथा u और v के अधिक विवरण और एल्गोरिदम के लिए सबसे छोटी पथ समस्या देखें।

छद्म-परिधीय शीर्ष खोजने के लिए एल्गोरिथम

प्रायः परिधीय विरल आव्यूह एल्गोरिदम को एक उच्च उत्केन्द्रता के साथ एक प्रारंभिक शीर्ष की आवश्यकता होती है। एक परिधीय शीर्ष सही होता है लेकिन प्रायः इसकी गणना करना कठिन होता है। अधिकांश स्थितियों में छद्म-परिधीय शीर्ष का उपयोग किया जा सकता है। निम्नलिखित एल्गोरिथम के साथ एक छद्म-परिधीय शीर्ष आसानी से पाया जा सकता है:

1. एक शीर्ष $u$ का चयन करे।
2. उन सभी शीर्षों में से जो यथासंभव $u$ से दूर हैं, माना कि $v$ न्यूनतम आरेख सिद्धांत है।
3. यदि $\epsilon (v)>\epsilon (u)$ तब $u=v$ और चरण 2 के साथ दोहराएँ अन्यथा $u$ एक छद्म-परिधीय शीर्ष है।

यह भी देखें

• दूरी आव्यूह
• प्रतिरोध दूरी
• बीच की केंद्रीयता
• केंद्रीयता
• निकटता (आरेख सिद्धांत)
• आरेख (असतत गणित) और दिशा आरेख (गणित) के लिए परिमाण व्यास की समस्या
• आव्यूह आरेख