दूरी (ग्राफ सिद्धांत): Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Length of shortest path between two nodes of a graph}} {{Redirect|Geodesic distance|distances on the surface of a sphere|Great-circle distance|distances on...")
 
No edit summary
 
(4 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Length of shortest path between two nodes of a graph}}
{{Short description|Length of shortest path between two nodes of a graph}}[[ग्राफ सिद्धांत|'''आरेख सिद्धांत''']] के गणितीय क्षेत्र में आरेख़ में दो शीर्षों के बीच की दूरी उन्हें संबद्ध करने वाले सबसे छोटे पथ (जिसे आरेख़ [[सबसे छोटी पथ समस्या|जियोडेसिक]] भी कहा जाता है) में शीर्षों की संख्या होती है। इसे जियोडेसिक दूरी या सबसे छोटी पथ दूरी के रूप में भी जाना जाता है।<ref>{{cite journal  
{{Redirect|Geodesic distance|distances on the surface of a sphere|Great-circle distance|distances on the surface of the Earth|Geodesics on an ellipsoid|geodesics in differential geometry|Geodesic}}
 
[[ग्राफ सिद्धांत]] के गणित क्षेत्र में, एक [[ग्राफ (असतत गणित)]] में दो वर्टेक्स (ग्राफ सिद्धांत) के बीच की दूरी उन्हें जोड़ने वाली [[सबसे छोटी पथ समस्या]] (जिसे ग्राफ जियोडेसिक भी कहा जाता है) में किनारों की संख्या है। इसे जियोडेसिक दूरी या सबसे छोटी पथ दूरी के रूप में भी जाना जाता है।<ref>{{cite journal  
  |last = Bouttier   
  |last = Bouttier   
  |first = Jérémie  
  |first = Jérémie  
Line 16: Line 13:
  |doi = 10.1016/S0550-3213(03)00355-9
  |doi = 10.1016/S0550-3213(03)00355-9
  |arxiv = cond-mat/0303272  
  |arxiv = cond-mat/0303272  
}}</ref> ध्यान दें कि दो शीर्षों के बीच एक से अधिक लघुतम पथ हो सकते हैं।<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=ग्राफ जियोडेसिक|access-date=2008-04-23 |last=Weisstein |first=Eric W. |author-link=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource |publisher=Wolfram Research |quote=इन बिंदुओं d(u,v) के बीच जियोडेसिक ग्राफ की लंबाई को u और v के बीच की ग्राफ दूरी कहा जाता है|archive-date=2008-04-23 |archive-url=https://web.archive.org/web/20080423071114/http://mathworld.wolfram.com/GraphGeodesic.html |url-status=live }}</ref> यदि दो शीर्षों को जोड़ने वाला कोई [[पथ (ग्राफ सिद्धांत)]] नहीं है, अर्थात, यदि वे अलग-अलग जुड़े घटक (ग्राफ सिद्धांत) से संबंधित हैं, तो पारंपरिक रूप से दूरी को अनंत के रूप में परिभाषित किया जाता है।
}}</ref> ध्यान दें कि दो शीर्षों के बीच एक से अधिक लघुतम पथ हो सकते हैं।<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=ग्राफ जियोडेसिक|access-date=2008-04-23 |last=Weisstein |first=Eric W. |author-link=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource |publisher=Wolfram Research |quote=इन बिंदुओं d(u,v) के बीच जियोडेसिक ग्राफ की लंबाई को u और v के बीच की ग्राफ दूरी कहा जाता है|archive-date=2008-04-23 |archive-url=https://web.archive.org/web/20080423071114/http://mathworld.wolfram.com/GraphGeodesic.html |url-status=live }}</ref> यदि दो शीर्षों को जोड़ने वाला कोई पथ नहीं है, अर्थात यदि वे विभिन्न संबद्ध घटकों से संबंधित हैं, तो पारंपरिक रूप से दूरी को अपरिमित के रूप में परिभाषित किया जाता है।


एक [[निर्देशित ग्राफ]] के मामले में दूरी {{math|''d''(''u'',''v'')}} दो शीर्षों के बीच {{mvar|u}} और {{mvar|v}} को सबसे छोटे निर्देशित पथ की लंबाई के रूप में परिभाषित किया गया है {{mvar|u}} को {{mvar|v}} चापों से युक्त, बशर्ते कम से कम एक ऐसा मार्ग मौजूद हो।<ref>F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.</ref> ध्यान दें कि, अप्रत्यक्ष रेखांकन के मामले के विपरीत, {{math|''d''(''u'',''v'')}} के साथ मेल खाना जरूरी नहीं है {{math|''d''(''v'',''u'')}}—तो यह सिर्फ एक मीट्रिक (गणित)#Quasimetrics|quasi-metric है, और यह मामला हो सकता है कि एक परिभाषित है जबकि दूसरा नहीं है।
एक [[निर्देशित ग्राफ|निर्देशित आरेख]] की स्थिति में दूरी {{math|''d''(''u'',''v'')}} दो शीर्षों {{mvar|u}} और {{mvar|v}} के बीच की दूरी को u से v तक सबसे छोटे निर्देशित पथ की लंबाई के रूप में परिभाषित किया गया है, जिसमें कम से कम एक पथ सम्मिलित होता है।<ref>F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.</ref> ध्यान दें कि, अप्रत्यक्ष रेखांकन की स्थिति के विपरीत {{math|''d''(''u'',''v'')}} आवश्यक नहीं कि {{math|''d''(''v'',''u'')}} के साथ अनुरूप है यह सिर्फ एक अर्ध-आव्यूह है और यह स्थिति हो सकती है कि एक को परिभाषित किया गया है जबकि दूसरे को परिभाषित नही किया गया है।


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


विलक्षणता {{math|''ϵ''(''v'')}} एक शीर्ष का {{mvar|v}} के बीच की सबसे बड़ी दूरी है {{mvar|v}} और कोई अन्य शीर्ष; प्रतीकों में,
किसी शीर्ष {{mvar|v}} की उत्केन्द्रता {{math|''ϵ''(''v'')}} और {{mvar|v}} किसी अन्य शीर्ष के बीच की अधिकतम दूरी होती है तब प्रतीकों में,
:<math>\epsilon(v) = \max_{u \in V}d(v,u).</math>
:<math>\epsilon(v) = \max_{u \in V}d(v,u).</math>
यह सोचा जा सकता है कि ग्राफ़ में नोड से सबसे दूर नोड से कितनी दूर है।
यह सोचा जा सकता है कि आरेख़ में नोड से सबसे दूर नोड से कितनी दूर है।


त्रिज्या {{mvar|r}किसी ग्राफ का } किसी भी शीर्ष का न्यूनतम विलक्षणता है या, प्रतीकों में,
आरेख़ की त्रिज्या r किसी भी शीर्ष की न्यूनतम विकेन्द्रता है या प्रतीकों में,
:<math>r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u).</math>
:<math>r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u).</math>


{{anchor|diameter}}व्यास {{mvar|d}ग्राफ़ का } ग्राफ़ में किसी भी शीर्ष की अधिकतम विलक्षणता है। वह है, {{mvar|d}} शीर्षों के किसी भी युग्म के बीच की सबसे बड़ी दूरी है या, वैकल्पिक रूप से,
किसी आरेख़ का व्यास d आरेख़ में किसी भी शीर्ष की अधिकतम उत्केन्द्रता है। अर्थात्, d शीर्षों के किसी भी युग्म के बीच की सबसे बड़ी दूरी है या वैकल्पिक रूप से,
:<math>d = \max_{v \in V}\epsilon(v) = \max_{v \in V}\max_{u \in V}d(v,u).</math>
:<math>d = \max_{v \in V}\epsilon(v) = \max_{v \in V}\max_{u \in V}d(v,u).</math>
एक ग्राफ के व्यास को खोजने के लिए, पहले शीर्ष (ग्राफ सिद्धांत) की प्रत्येक जोड़ी के बीच सबसे छोटी पथ समस्या का पता लगाएं। इनमें से किसी भी पथ की सबसे बड़ी लंबाई ग्राफ़ का व्यास है।
किसी आरेख़ का व्यास ज्ञात करने के लिए, पहले प्रत्येक युग्म के शीर्षों के बीच सबसे छोटा पथ ज्ञात करें। इनमें से किसी भी पथ की सबसे बड़ी लंबाई आरेख़ का व्यास है। त्रिज्या r के एक आरेख में एक केंद्रीय शीर्ष वह है जिसका उत्केन्द्रता {{mvar|r}} है अर्थात, एक शीर्ष जिसकी दूरी उसके सबसे दूर के शीर्ष से त्रिज्या के समकक्ष के बराबर है एक शीर्ष {{mvar|v}} जैसे कि {{math|1=''ϵ''(''v'') = ''r''}} व्यास {{mvar|d}} के आरेख़ में एक परिधीय शीर्ष वह है जिसकी उत्केन्द्रता {{mvar|d}} है अर्थात्, एक शीर्ष जिसकी दूरतम शीर्ष से दूरी व्यास के बराबर है। औपचारिक रूप से, {{mvar|v}} परिधीय है यदि {{math|1=''ϵ''(''v'') = ''d''}} छद्म-परिधीय शीर्ष v में यह गुण होता है कि, किसी भी शीर्ष u के लिए, यदि u यथासंभव v से दूर है, तो v यथासंभव दूर है। औपचारिक रूप से, एक शीर्ष {{mvar|v}} छद्म-परिधीय होता है यदि प्रत्येक शीर्ष {{mvar|u}} के लिए {{math|1=''d''(''u'',''v'') = ''ϵ''(''v'')}} के साथ, यह मानता है कि {{math|1=''ϵ''(''u'') = ''ϵ''(''v'')}} आरेख़ की एक स्तर संरचना, एक प्रारंभिक शीर्ष दिया गया है प्रारंभिक शीर्ष से उनकी दूरी के आधार पर आरेख़ के शीर्ष का उप समुच्चय में विभाजन है।


त्रिज्या के ग्राफ में एक केंद्रीय शीर्ष {{mvar|r}} वह है जिसकी विलक्षणता है {{mvar|r}}—अर्थात्, एक शीर्ष जिसकी सबसे दूर के शीर्ष से दूरी त्रिज्या के बराबर है, समतुल्य, एक शीर्ष {{mvar|v}} ऐसा है कि {{math|1=''ϵ''(''v'') = ''r''}}.
एक [[जियोडेटिक ग्राफ|जियोडेटिक आरेख]] वह होता है जिसके लिए प्रत्येक जोड़े के शीर्ष में उन्हें जोड़ने वाला एक अन्य सबसे छोटा पथ होता है। उदाहरण के लिए, सभी पेड़ जियोडेटिक होते हैं।<ref>[[Øystein Ore]], Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104</ref>


व्यास के ग्राफ में एक परिधीय शीर्ष {{mvar|d}} वह है जिसकी विलक्षणता है {{mvar|d}}—अर्थात्, एक शीर्ष जिसकी सबसे दूरस्थ शीर्ष से दूरी व्यास के बराबर है। औपचारिक रूप से, {{mvar|v}} परिधीय है अगर {{math|1=''ϵ''(''v'') = ''d''}}.
भारित सबसे छोटी-पथ दूरी, भारित आरेख़ के लिए जियोडेसिक दूरी का सामान्यीकरण करता है। इस स्थिति में यह माना जाता है कि शीर्ष का भार इसकी लंबाई का प्रतिनिधित्व करता है या जटिल नेटवर्क के लिए परस्पर क्रिया की लागत और भारित सबसे छोटी-पथ दूरी {{math|''d''{{sup|''W''}}(''u'', ''v'')}} को संबद्ध करने वाले सभी पथों में भार का न्यूनतम योग है तथा {{mvar|u}} और {{mvar|v}} के अधिक विवरण और एल्गोरिदम के लिए सबसे छोटी पथ समस्या देखें।


एक छद्म-परिधीय शीर्ष {{mvar|v}} में वह गुण है जो किसी शीर्ष के लिए है {{mvar|u}}, अगर {{mvar|u}} से बहुत दूर है {{mvar|v}} जितना संभव हो, तब {{mvar|v}} से बहुत दूर है {{mvar|u}} यथासंभव। औपचारिक रूप से, एक शिखर {{mvar|v}} छद्म-परिधीय है यदि, प्रत्येक शीर्ष के लिए {{mvar|u}} साथ {{math|1=''d''(''u'',''v'') = ''ϵ''(''v'')}}, यह मानता है {{math|1=''ϵ''(''u'') = ''ϵ''(''v'')}}.
== छद्म-परिधीय शीर्ष खोजने के लिए एल्गोरिथम ==
प्रायः परिधीय विरल आव्यूह एल्गोरिदम को एक उच्च उत्केन्द्रता के साथ एक प्रारंभिक शीर्ष की आवश्यकता होती है। एक परिधीय शीर्ष सही होता है लेकिन प्रायः इसकी गणना करना कठिन होता है। अधिकांश स्थितियों में छद्म-परिधीय शीर्ष का उपयोग किया जा सकता है। निम्नलिखित एल्गोरिथम के साथ एक छद्म-परिधीय शीर्ष आसानी से पाया जा सकता है:


ग्राफ़ की एक स्तरीय संरचना, जिसे एक प्रारंभिक शीर्ष दिया गया है, ग्राफ़ के शीर्षों के एक सेट का एक विभाजन है जो प्रारंभिक शीर्ष से उनकी दूरी के आधार पर सबसेट में होता है।
# एक शीर्ष <math>u</math> का चयन करे।
 
# उन सभी शीर्षों में से जो यथासंभव <math>u</math> से दूर हैं, माना कि <math>v</math> न्यूनतम [[डिग्री (ग्राफ सिद्धांत)|आरेख सिद्धांत]] है।
एक [[जियोडेटिक ग्राफ]] वह होता है जिसके लिए प्रत्येक जोड़े के कोने में उन्हें जोड़ने वाला एक अनूठा सबसे छोटा रास्ता होता है। उदाहरण के लिए, सभी ट्री (ग्राफ़ थ्योरी) जियोडेटिक हैं।<ref>[[Øystein Ore]], Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society,  p. 104</ref>
# यदि <math>\epsilon(v) > \epsilon(u)</math> तब <math>u=v</math> और चरण 2 के साथ दोहराएँ अन्यथा <math>u</math> एक छद्म-परिधीय शीर्ष है।
वेटेड शॉर्टेस्ट-पाथ डिस्टेंस जियोडेसिक डिस्टेंस को ग्राफ़ थ्योरी # weighted_graph की ग्लोसरी के लिए सामान्यीकृत करता है। इस मामले में यह माना जाता है कि किनारे का वजन इसकी लंबाई का प्रतिनिधित्व करता है या, [[जटिल नेटवर्क]] के लिए बातचीत की लागत, और भारित सबसे छोटी-पथ दूरी {{math|''d''{{sup|''W''}}(''u'', ''v'')}} सभी शब्दावली_ऑफ_ग्राफ_थ्योरी#पथ कनेक्टिंग में भार का न्यूनतम योग है {{mvar|u}} और {{mvar|v}}. अधिक विवरण और एल्गोरिदम के लिए सबसे छोटी पथ समस्या देखें।
 
== छद्म-परिधीय कोने खोजने के लिए एल्गोरिथम ==
अक्सर परिधीय [[विरल मैट्रिक्स]] एल्गोरिदम को एक उच्च विलक्षणता के साथ एक प्रारंभिक शीर्ष की आवश्यकता होती है। एक परिधीय शीर्ष एकदम सही होगा, लेकिन अक्सर इसकी गणना करना कठिन होता है। ज्यादातर परिस्थितियों में छद्म-परिधीय शीर्ष का उपयोग किया जा सकता है। निम्नलिखित एल्गोरिथम के साथ एक छद्म-परिधीय शीर्ष आसानी से पाया जा सकता है:
 
# शीर्ष चुनें <math>u</math>.
# उन सभी शीर्षों के बीच जो दूर हैं <math>u</math> जितना संभव हो, चलो <math>v</math> न्यूनतम [[डिग्री (ग्राफ सिद्धांत)]] के साथ एक बनें।
# अगर <math>\epsilon(v) > \epsilon(u)</math> फिर सेट करें <math>u=v</math> और चरण 2 के साथ दोहराएँ, अन्यथा <math>u</math> एक छद्म-परिधीय शीर्ष है।


== यह भी देखें ==
== यह भी देखें ==
{{col div|colwidth=40em}}
{{col div|colwidth=40em}}
* [[दूरी मैट्रिक्स]]
* [[दूरी आव्यूह]]
* [[प्रतिरोध दूरी]]
* [[प्रतिरोध दूरी]]
* बीचपन केंद्रीयता
* बीच की केंद्रीयता
* केंद्रीयता
* केंद्रीयता
* [[निकटता (ग्राफ सिद्धांत)]]
* [[निकटता (आरेख सिद्धांत)]]
* ग्राफ (असतत गणित) और [[डिग्राफ (गणित)]] के लिए [[डिग्री व्यास की समस्या]]
* आरेख (असतत गणित) और [[दिशा आरेख (गणित)]] के लिए [[परिमाण व्यास की समस्या]]
* [[मीट्रिक ग्राफ]]
* [[आव्यूह आरेख]]
{{colend}}
{{colend}}


==टिप्पणियाँ==
==टिप्पणियाँ==
{{reflist}}
{{reflist}}
[[Category: ग्राफ सिद्धांत]] [[Category: मीट्रिक ज्यामिति]] [[Category: ग्राफ डिस्टन्स]] [[Category: ग्राफ डिस्टन्स]] [Category:Graph distance


[[Category: Machine Translated Page]]
[[Category:Created On 20/03/2023]]
[[Category:Created On 20/03/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Multi-column templates]]
[[Category:Pages using div col with small parameter]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Templates using under-protected Lua modules]]
[[Category:Wikipedia fully protected templates|Div col]]
[[Category:ग्राफ डिस्टन्स]]
[[Category:ग्राफ सिद्धांत]]
[[Category:मीट्रिक ज्यामिति]]

Latest revision as of 18:26, 15 April 2023

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

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

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

टिप्पणियाँ

  1. ↑ Bouttier, Jérémie; Di Francesco,P.; Guitter, E. (July 2003). "Geodesic distance in planar graphs". Nuclear Physics B. 663 (3): 535–567. arXiv:cond-mat/0303272. doi:10.1016/S0550-3213(03)00355-9. By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
  2. ↑ Weisstein, Eric W. "ग्राफ जियोडेसिक". MathWorld--A Wolfram Web Resource. Wolfram Research. Archived from the original on 2008-04-23. Retrieved 2008-04-23. इन बिंदुओं d(u,v) के बीच जियोडेसिक ग्राफ की लंबाई को u और v के बीच की ग्राफ दूरी कहा जाता है
  3. ↑ F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
  4. ↑ Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=दूरी_(ग्राफ_सिद्धांत)&oldid=133615’