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

"Geodesic distance" redirects here. For distances on the surface of a sphere, see Great-circle distance. For distances on the surface of the Earth, see Geodesics on an ellipsoid. For geodesics in differential geometry, see Geodesic.

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

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

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

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

विलक्षणता ϵ(v) एक शीर्ष का v के बीच की सबसे बड़ी दूरी है v और कोई अन्य शीर्ष; प्रतीकों में,

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

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

त्रिज्या {{mvar|r}किसी ग्राफ का } किसी भी शीर्ष का न्यूनतम विलक्षणता है या, प्रतीकों में,

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

व्यास {{mvar|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 से बहुत दूर है u यथासंभव। औपचारिक रूप से, एक शिखर v छद्म-परिधीय है यदि, प्रत्येक शीर्ष के लिए u साथ d(u,v) = ϵ(v), यह मानता है ϵ(u) = ϵ(v).

ग्राफ़ की एक स्तरीय संरचना, जिसे एक प्रारंभिक शीर्ष दिया गया है, ग्राफ़ के शीर्षों के एक सेट का एक विभाजन है जो प्रारंभिक शीर्ष से उनकी दूरी के आधार पर सबसेट में होता है।

एक जियोडेटिक ग्राफ वह होता है जिसके लिए प्रत्येक जोड़े के कोने में उन्हें जोड़ने वाला एक अनूठा सबसे छोटा रास्ता होता है। उदाहरण के लिए, सभी ट्री (ग्राफ़ थ्योरी) जियोडेटिक हैं। वेटेड शॉर्टेस्ट-पाथ डिस्टेंस जियोडेसिक डिस्टेंस को ग्राफ़ थ्योरी # weighted_graph की ग्लोसरी के लिए सामान्यीकृत करता है। इस मामले में यह माना जाता है कि किनारे का वजन इसकी लंबाई का प्रतिनिधित्व करता है या, जटिल नेटवर्क के लिए बातचीत की लागत, और भारित सबसे छोटी-पथ दूरी d^W(u, v) सभी शब्दावली_ऑफ_ग्राफ_थ्योरी#पथ कनेक्टिंग में भार का न्यूनतम योग है u और v. अधिक विवरण और एल्गोरिदम के लिए सबसे छोटी पथ समस्या देखें।

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

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

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

यह भी देखें

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

टिप्पणियाँ

[Category:Graph distance