ग्रीडी एम्बेडिंग: Difference between revisions
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
==परिभाषाएँ== | ==परिभाषाएँ== | ||
लालची मार्ग में, स्रोत नोड एस से गंतव्य नोड | लालची मार्ग में, स्रोत नोड एस से गंतव्य नोड t तक संदेश मध्यवर्ती नोड्स के माध्यम से चरणों के अनुक्रम द्वारा अपने गंतव्य तक जाता है, जिनमें से प्रत्येक संदेश को निकटतम नोड पर भेजता है, जो t के समीप होता है। यदि संदेश मध्यवर्ती नोड x तक पहुंचता है जिसका कोई निकटतम t के समीप नहीं होता है, तब यह प्रगति नहीं कर सकता है और लालची मार्ग प्रक्रिया विफल हो जाती है। इस प्रकार लालची एम्बेडिंग दिए गए रेखा-चित्र को इस संपत्ति के साथ एम्बेड करता है कि इस प्रकार की विफलता असंभव होती है। इस प्रकार, इसे इस गुण के साथ रेखा-चित्र के एम्बेडिंग के रूप में वर्णित किया जा सकता है कि प्रत्येक दो नोड्स x और t के लिए, x का निकटतम y उपस्तिथ होता है जैसे कि d(x,t) > d(y,t), जहां d एम्बेडेड स्थान में दूरी दर्शाता है।<ref name="pr05"/> | ||
==बिना लालची एम्बेडिंग वाले रेखा-चित्र== | ==बिना लालची एम्बेडिंग वाले रेखा-चित्र== | ||
[[File:Sextic-monomial-dessin.svg|thumb|150px|K<sub>1,6</sub>, यूक्लिडियन सतह में कोई लालची एम्बेडिंग वाला रेखा-चित्र]]प्रत्येक रेखा-चित्र में [[यूक्लिडियन विमान|यूक्लिडियन सतह]] में लालची एम्बेडिंग नहीं होती है। इस प्रकार सरल प्रति उदाहरण [[तारा]] (रेखा-चित्र सिद्धांत) K<sub>1,6</sub> द्वारा दिया गया है, अतः आंतरिक नोड और छह पत्तियों वाला पेड़ (रेखा-चित्र सिद्धांत)<ref name="pr05"/> जब भी इस रेखा-चित्र को समतल में एम्बेड किया जाता है, तब इसकी कुछ दो पत्तियों को 60 डिग्री या उससे कम का कोण बनाता है, जिससे यह पता चलता है कि इन दो पत्तियों में से कम से कम का निकटतम दूसरे पत्ते के समीप नहीं होता है। | [[File:Sextic-monomial-dessin.svg|thumb|150px|K<sub>1,6</sub>, यूक्लिडियन सतह में कोई लालची एम्बेडिंग वाला रेखा-चित्र]]प्रत्येक रेखा-चित्र में [[यूक्लिडियन विमान|यूक्लिडियन सतह]] में लालची एम्बेडिंग नहीं होती है। इस प्रकार सरल प्रति उदाहरण [[तारा]] (रेखा-चित्र सिद्धांत) K<sub>1,6</sub> द्वारा दिया गया है, अतः आंतरिक नोड और छह पत्तियों वाला पेड़ (रेखा-चित्र सिद्धांत)<ref name="pr05"/> जब भी इस रेखा-चित्र को समतल में एम्बेड किया जाता है, तब इसकी कुछ दो पत्तियों को 60 डिग्री या उससे कम का कोण बनाता है, जिससे यह पता चलता है कि इन दो पत्तियों में से कम से कम का निकटतम दूसरे पत्ते के समीप नहीं होता है। | ||
| Line 18: | Line 18: | ||
अधिक सामान्य रेखा-चित्र के लिए, कुछ लालची एम्बेडिंग एल्गोरिदम जैसे कि क्लेनबर्ग<ref name="k07"/> द्वारा दिए गए रेखा-चित्र का स्पैनिंग पेड़ खोजकर प्रारंभ करते है और फिर स्पैनिंग पेड़ का लालची एम्बेडिंग का निर्माण करते हैं। इस प्रकार परिणाम आवश्यक रूप से पूरे रेखा-चित्र का लालची एम्बेडिंग भी होता है। चूँकि, ऐसे रेखा-चित्र उपस्तिथ होते हैं जिनमें यूक्लिडियन सतह में लालची एम्बेडिंग होते है, किन्तु जिनके लिए किसी भी फैले हुए पेड़ में लालची एम्बेडिंग नहीं होते है।<ref name="lm10"/> | अधिक सामान्य रेखा-चित्र के लिए, कुछ लालची एम्बेडिंग एल्गोरिदम जैसे कि क्लेनबर्ग<ref name="k07"/> द्वारा दिए गए रेखा-चित्र का स्पैनिंग पेड़ खोजकर प्रारंभ करते है और फिर स्पैनिंग पेड़ का लालची एम्बेडिंग का निर्माण करते हैं। इस प्रकार परिणाम आवश्यक रूप से पूरे रेखा-चित्र का लालची एम्बेडिंग भी होता है। चूँकि, ऐसे रेखा-चित्र उपस्तिथ होते हैं जिनमें यूक्लिडियन सतह में लालची एम्बेडिंग होते है, किन्तु जिनके लिए किसी भी फैले हुए पेड़ में लालची एम्बेडिंग नहीं होते है।<ref name="lm10"/> | ||
===समतलीय रेखांकन=== | ===समतलीय रेखांकन=== | ||
{{unsolved| | {{unsolved|गणितीय|क्या प्रत्येक [[बहुफलकीय ग्राफ]] में उत्तल फलकों के साथ समतलीय लालची एम्बेडिंग होती है?}} | ||
{{harvtxt|पापादिमित्रियोउ|रतज्ज़क|2005}} ने [[अनुमान]] लगाया गया था कि प्रत्येक [[पॉलीहेड्रल ग्राफ| | {{harvtxt|पापादिमित्रियोउ|रतज्ज़क|2005}} ने [[अनुमान]] लगाया गया था कि प्रत्येक [[पॉलीहेड्रल ग्राफ|बहुफलकीय रेखा-चित्र]] ([[3-वर्टेक्स-कनेक्टेड|3-शिखर-संयुक्त]] [[ समतलीय ग्राफ |समतलीय रेखा-चित्र]], या [[स्टीनिट्ज़ की]] [[प्रमेय]] के अनुसार समतुल्य [[उत्तल पॉलीहेड्रॉन|उत्तल बहुतल]] का रेखा-चित्र) में यूक्लिडियन सतह में लालची एम्बेडिंग होती है।<ref name="pr05"/> इस प्रकार [[कैक्टस ग्राफ|कैक्टस रेखा-चित्र]] के गुणों का दोहन करके, {{harvtxt|लीटन|मोइत्रा|2010}} ने अनुमान सिद्ध हुआ था।<ref name="lm10"/><ref name="afg10"/> इन रेखा-चित्रों की लालची एम्बेडिंग को लघुगणकीय रूप से प्रति समन्वय अनेक बिट्स के साथ संक्षेप में परिभाषित किया जा सकता है।<ref name="gs09"/> चूँकि, इस प्रमाण के अनुसार निर्मित लालची एम्बेडिंग आवश्यक रूप से समतल एम्बेडिंग नहीं होती हैं, जिससे कि उनमें किनारों के जोड़े के मध्य क्रॉसिंग सम्मिलित हो सकती है। सामान्यतः [[अधिकतम समतलीय रेखांकन]] के लिए, जिसमें प्रत्येक फलक त्रिभुज होता है, अतः श्नाइडर के [[सीधी-रेखा एम्बेडिंग]] एल्गोरिदम भारित संस्करण में [[नैस्टर-कुराटोव्स्की-मज़ुरकिविज़ लेम्मा]] को क्रियान्वित करके लालची समतलीय एम्बेडिंग पाई जा सकती है।<ref name="s90"/><ref name="d10"/> इस प्रकार '''मजबूत पापादिमित्रीउ-रतज्ज़क''' '''अनुमान''', कि प्रत्येक [[बहुफलकीय ग्राफ|बहुफलकीय रेखा-चित्र]] में समतलीय लालची एम्बेडिंग होती है जिसमें सभी सम्मुख उत्तल होते हैं, अतः वह अप्रमाणित रहता है।<ref>{{citation | ||
| last1 = Nöllenburg | first1 = Martin | | last1 = Nöllenburg | first1 = Martin | ||
| last2 = Prutkin | first2 = Roman | | last2 = Prutkin | first2 = Roman | ||
Revision as of 00:02, 7 July 2023
वितरित कंप्यूटिंग और ज्यामितीय रेखा-चित्र सिद्धांत में, लालची एम्बेडिंग दूरसंचार नेटवर्क के नोड्स को निर्देशांक निर्दिष्ट करने की प्रक्रिया होती है जिससे कि नेटवर्क के अंदर संदेशों को क्रम करने के लिए लालची एल्गोरिदम भौगोलिक मार्ग का उपयोग करने की अनुमति मिल सकती है। यद्यपि वायरलेस सेंसर नेटवर्क में उपयोग के लिए लालची एम्बेडिंग का प्रस्ताव किया गया है, जिसमें नोड्स के पास पहले से ही भौतिक स्थान में स्थिति होती है, यह उपस्तिथ स्थिति लालची एम्बेडिंग द्वारा उन्हें दी गई स्थिति से भिन्न हो सकती हैं, जो कुछ स्थितियों में आभासी स्थान में बिंदु हो सकती हैं, अतः उच्च आयाम का या गैर-यूक्लिडियन ज्यामिति में इस अर्थ में, लालची एम्बेडिंग को रेखा-चित्र चित्रकला के रूप के रूप में देखा जा सकता है, जिसमें अमूर्त रेखा-चित्र (संचार नेटवर्क) ज्यामितीय स्थान में रेखा-चित्र एम्बेडिंग होता है।
भौतिक निर्देशांक का उपयोग करने के अतिरिक्त, आभासी स्थान में निर्देशांक का उपयोग करके भौगोलिक क्रम करने का विचार राव एट अल के कारण होता है।[1] इस प्रकार बाद के विकासों से पता चलता है कि प्रत्येक नेटवर्क में अतिशयोक्तिपूर्ण सतह में संक्षिप्त शीर्ष निर्देशांक के साथ लालची एम्बेडिंग होती है कि बहुफलकीय रेखा-चित्र सहित कुछ रेखा-चित्र में यूक्लिडियन सतह में लालची एम्बेडिंग होती है और इकाई डिस्क रेखा-चित्र में मध्यम आयामों के कम खिंचाव कारक यूक्लिडियन स्थानों में लालची एम्बेडिंग होती है।
परिभाषाएँ
लालची मार्ग में, स्रोत नोड एस से गंतव्य नोड t तक संदेश मध्यवर्ती नोड्स के माध्यम से चरणों के अनुक्रम द्वारा अपने गंतव्य तक जाता है, जिनमें से प्रत्येक संदेश को निकटतम नोड पर भेजता है, जो t के समीप होता है। यदि संदेश मध्यवर्ती नोड x तक पहुंचता है जिसका कोई निकटतम t के समीप नहीं होता है, तब यह प्रगति नहीं कर सकता है और लालची मार्ग प्रक्रिया विफल हो जाती है। इस प्रकार लालची एम्बेडिंग दिए गए रेखा-चित्र को इस संपत्ति के साथ एम्बेड करता है कि इस प्रकार की विफलता असंभव होती है। इस प्रकार, इसे इस गुण के साथ रेखा-चित्र के एम्बेडिंग के रूप में वर्णित किया जा सकता है कि प्रत्येक दो नोड्स x और t के लिए, x का निकटतम y उपस्तिथ होता है जैसे कि d(x,t) > d(y,t), जहां d एम्बेडेड स्थान में दूरी दर्शाता है।[2]
बिना लालची एम्बेडिंग वाले रेखा-चित्र
प्रत्येक रेखा-चित्र में यूक्लिडियन सतह में लालची एम्बेडिंग नहीं होती है। इस प्रकार सरल प्रति उदाहरण तारा (रेखा-चित्र सिद्धांत) K1,6 द्वारा दिया गया है, अतः आंतरिक नोड और छह पत्तियों वाला पेड़ (रेखा-चित्र सिद्धांत)[2] जब भी इस रेखा-चित्र को समतल में एम्बेड किया जाता है, तब इसकी कुछ दो पत्तियों को 60 डिग्री या उससे कम का कोण बनाता है, जिससे यह पता चलता है कि इन दो पत्तियों में से कम से कम का निकटतम दूसरे पत्ते के समीप नहीं होता है।
उच्च आयामों के यूक्लिडियन स्थानों में, अधिक रेखा-चित्र में लालची एम्बेडिंग हो सकती है। उदाहरण के लिए, K1,6 में त्रि-आयामी यूक्लिडियन अंतरिक्ष में लालची एम्बेडिंग होता है, जिसमें तारे का आंतरिक नोड मूल पर है और पत्तियां प्रत्येक समन्वय अक्ष के साथ इकाई की दूरी पर होती हैं। चूँकि, निश्चित आयाम के प्रत्येक यूक्लिडियन स्थान के लिए, ऐसे रेखा-चित्र होते हैं जिन्हें लालच से एम्बेड नहीं किया जा सकता है। इस प्रकार जब भी संख्या n अंतरिक्ष की चुंबन संख्या समस्या से अधिक होती है, तब रेखा-चित्र K1,n कोई लालची एम्बेडिंग नहीं होता है।[3]
अतिशयोक्तिपूर्ण और संक्षिप्त एम्बेडिंग
यूक्लिडियन सतह की स्थिति के विपरीत, प्रत्येक नेटवर्क में हाइपरबोलिक सतह में लालची एम्बेडिंग होती है। इस परिणाम के मूल प्रमाण में, रॉबर्ट क्लेनबर्ग द्वारा, नोड स्थितियों को उच्च परिशुद्धता के साथ निर्दिष्ट करने की आवश्यकता होती थी,[4] किन्तु बाद में यह दिखाया गया था कि, नेटवर्क के फैले हुए पेड़ के भारी पथ अपघटन का उपयोग करके, यह संभव हुआ है कि प्रति बिंदु बिट्स की केवल लघुगणकीय संख्या का उपयोग करके, प्रत्येक नोड को संक्षेप में प्रस्तुत करना संभव होता है।[3] इसके विपरीत, ऐसे रेखा-चित्र उपस्तिथ होते हैं जिनमें यूक्लिडियन सतह में लालची एम्बेडिंग होते है, किन्तु जिसके लिए ऐसे किसी भी एम्बेडिंग के लिए प्रत्येक बिंदु के कार्टेशियन निर्देशांक के लिए बिट्स की बहुपद संख्या की आवश्यकता होती है।[5][6]
रेखा-चित्र के विशेष वर्ग
पेड़
यूक्लिडियन सतह में लालची एम्बेडिंग को स्वीकार करने वाले पेड़ों के वर्ग (रेखा-चित्र सिद्धांत) को पूर्ण प्रकार से चित्रित किया गया है और पेड़ की लालची एम्बेडिंग रैखिक समय में पाया जा सकता है जब वह उपस्तिथ होता है।[7]
अधिक सामान्य रेखा-चित्र के लिए, कुछ लालची एम्बेडिंग एल्गोरिदम जैसे कि क्लेनबर्ग[4] द्वारा दिए गए रेखा-चित्र का स्पैनिंग पेड़ खोजकर प्रारंभ करते है और फिर स्पैनिंग पेड़ का लालची एम्बेडिंग का निर्माण करते हैं। इस प्रकार परिणाम आवश्यक रूप से पूरे रेखा-चित्र का लालची एम्बेडिंग भी होता है। चूँकि, ऐसे रेखा-चित्र उपस्तिथ होते हैं जिनमें यूक्लिडियन सतह में लालची एम्बेडिंग होते है, किन्तु जिनके लिए किसी भी फैले हुए पेड़ में लालची एम्बेडिंग नहीं होते है।[8]
समतलीय रेखांकन
क्या प्रत्येक बहुफलकीय ग्राफ में उत्तल फलकों के साथ समतलीय लालची एम्बेडिंग होती है?
पापादिमित्रियोउ & रतज्ज़क (2005) ने अनुमान लगाया गया था कि प्रत्येक बहुफलकीय रेखा-चित्र (3-शिखर-संयुक्त समतलीय रेखा-चित्र, या स्टीनिट्ज़ की प्रमेय के अनुसार समतुल्य उत्तल बहुतल का रेखा-चित्र) में यूक्लिडियन सतह में लालची एम्बेडिंग होती है।[2] इस प्रकार कैक्टस रेखा-चित्र के गुणों का दोहन करके, लीटन & मोइत्रा (2010) ने अनुमान सिद्ध हुआ था।[8][9] इन रेखा-चित्रों की लालची एम्बेडिंग को लघुगणकीय रूप से प्रति समन्वय अनेक बिट्स के साथ संक्षेप में परिभाषित किया जा सकता है।[10] चूँकि, इस प्रमाण के अनुसार निर्मित लालची एम्बेडिंग आवश्यक रूप से समतल एम्बेडिंग नहीं होती हैं, जिससे कि उनमें किनारों के जोड़े के मध्य क्रॉसिंग सम्मिलित हो सकती है। सामान्यतः अधिकतम समतलीय रेखांकन के लिए, जिसमें प्रत्येक फलक त्रिभुज होता है, अतः श्नाइडर के सीधी-रेखा एम्बेडिंग एल्गोरिदम भारित संस्करण में नैस्टर-कुराटोव्स्की-मज़ुरकिविज़ लेम्मा को क्रियान्वित करके लालची समतलीय एम्बेडिंग पाई जा सकती है।[11][12] इस प्रकार मजबूत पापादिमित्रीउ-रतज्ज़क अनुमान, कि प्रत्येक बहुफलकीय रेखा-चित्र में समतलीय लालची एम्बेडिंग होती है जिसमें सभी सम्मुख उत्तल होते हैं, अतः वह अप्रमाणित रहता है।[13]
इकाई डिस्क रेखा-चित्र
सामान्यतः बिना तार का यंत्र नियंत्रक नेटवर्क जो लालची कैक्टस रेखा-चित्र एम्बेडिंग एल्गोरिदम का लक्ष्य होता हैं, उन्हें अधिकांशतः इकाई डिस्क रेखा-चित्र के रूप में मॉडल किया जाता है, चूँकि रेखा-चित्र जिसमें प्रत्येक नोड को इकाई डिस्क के रूप में दर्शाया जाता है और प्रत्येक किनारा गैर-रिक्त चौराहे के साथ डिस्क की जोड़ी से मेल खाता है। इस प्रकार रेखा-चित्र के इस विशेष वर्ग के लिए, बहु लयबद्ध आयाम के यूक्लिडियन स्थान में संक्षिप्त लालची एम्बेडिंग को खोजना संभव होता है, अतः अतिरिक्त संपत्ति के साथ रेखा-चित्र में दूरियों को एम्बेडिंग में दूरियों द्वारा त्रुटिहीन रूप से अनुमानित किया जाता है, जिससे कि लालची मार्ग द्वारा अपनाए गए पथ संक्षिप्त होते है।[14]
संदर्भ
- ↑ Rao, Ananth; Ratnasamy, Sylvia; Papadimitriou, Christos H.; Shenker, Scott; Stoica, Ion (2003), "Geographic routing without location information", Proc. 9th ACM Mobile Computing and Networking (MobiCom), pp. 96–108, doi:10.1145/938985.938996.
- ↑ 2.0 2.1 2.2 Papadimitriou, Christos H.; Ratajczak, David (2005), "On a conjecture related to geometric routing", Theoretical Computer Science, 344 (1): 3–14, doi:10.1016/j.tcs.2005.06.022, MR 2178923.
- ↑ 3.0 3.1 Eppstein, D.; Goodrich, M. T. (2011), "Succinct greedy geometric routing using hyperbolic geometry", IEEE Transactions on Computers, 60 (11): 1571–1580, doi:10.1109/TC.2010.257.
- ↑ 4.0 4.1 Kleinberg, R. (2007), "Geographic routing using hyperbolic space", Proc. 26th IEEE International Conference on Computer Communications (INFOCOM 2007), pp. 1902–1909, doi:10.1109/INFCOM.2007.221.
- ↑ Cao, Lei; Strelzoff, A.; Sun, J. Z. (2009), "On succinctness of geometric greedy routing in Euclidean plane", 10th International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN 2009), pp. 326–331, doi:10.1109/I-SPAN.2009.20.
- ↑ Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio (2010), "Succinct greedy drawings do not always exist", Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, pp. 171–182, doi:10.1007/978-3-642-11805-0_17.
- ↑ Nöllenburg, Martin; Prutkin, Roman (2013), "Euclidean greedy drawings of trees", Proc. 21st European Symposium on Algorithms (ESA 2013), arXiv:1306.5224, Bibcode:2013arXiv1306.5224N.
- ↑ 8.0 8.1 Leighton, Tom; Moitra, Ankur (2010), "Some results on greedy embeddings in metric spaces", Discrete and Computational Geometry, 44 (3): 686–705, doi:10.1007/s00454-009-9227-6, MR 2679063.
- ↑ Angelini, Patrizio; Frati, Fabrizio; Grilli, Luca (2010), "An algorithm to construct greedy drawings of triangulations", Journal of Graph Algorithms and Applications, 14 (1): 19–51, doi:10.7155/jgaa.00197, MR 2595019.
- ↑ Goodrich, Michael T.; Strash, Darren (2009), "Succinct greedy geometric routing in the Euclidean plane", Algorithms and Computation: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009, Proceedings, Lecture Notes in Computer Science, vol. 5878, Berlin: Springer, pp. 781–791, arXiv:0812.3893, doi:10.1007/978-3-642-10631-6_79, MR 2792775.
- ↑ Schnyder, Walter (1990), "Embedding planar graphs on the grid", Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138–148.
- ↑ Dhandapani, Raghavan (2010), "Greedy drawings of triangulations", Discrete and Computational Geometry, 43 (2): 375–392, doi:10.1007/s00454-009-9235-6, MR 2579703. See also
- ↑ Nöllenburg, Martin; Prutkin, Roman; Rutter, Ignaz (2016), "On self-approaching and increasing-chord drawings of 3-connected planar graphs", Journal of Computational Geometry, 7 (1): 47–69, arXiv:1409.0315, doi:10.20382/jocg.v7i1a3, MR 3463906.
- ↑ Flury, R.; Pemmaraju, S.V.; Wattenhofer, R. (2009), "Greedy routing with bounded stretch", IEEE INFOCOM 2009, pp. 1737–1745, doi:10.1109/INFCOM.2009.5062093.
