वृद्धि गुणक: Difference between revisions

From Vigyanwiki
(Created page with "{{Use American English|date = February 2019}} {{Short description|Mathematical parameter of embeddings}} {{Use mdy dates|date = February 2019}} {{distinguish|text=the stretch...")
 
(tetxt)
Line 1: Line 1:
{{Use American English|date = February 2019}}
 
{{Short description|Mathematical parameter of embeddings}}
{{Short description|Mathematical parameter of embeddings}}
{{Use mdy dates|date = February 2019}}
{{distinguish|text=the stretch factor of a [[pseudo-Anosov map]]}}
[[एम्बेडिंग]] का खिंचाव कारक (यानी, लिप्सचिट्ज़ निरंतरता#परिभाषा) उस कारक को मापता है जिसके द्वारा एम्बेडिंग दूरियों को विकृत करता है। मान लीजिए कि एक [[मीट्रिक स्थान]] {{mvar|S}} किसी अन्य मीट्रिक स्थान में एम्बेडेड है {{mvar|T}} एक [[मीट्रिक मानचित्र]] द्वारा, एक सतत एक-से-एक फ़ंक्शन {{mvar|f}} जो प्रत्येक जोड़ी बिंदुओं के बीच की दूरी को संरक्षित या कम करता है। फिर एम्बेडिंग बिंदुओं के जोड़े के बीच की दूरी की दो अलग-अलग धारणाओं को जन्म देती है {{mvar|S}}. अंकों का कोई भी जोड़ा {{math|(''x'',''y'')}} में {{mvar|S}} में एक [[आंतरिक मीट्रिक]], से दूरी दोनों हैं {{mvar|x}} को {{mvar|y}} में {{mvar|S}}, और एक छोटी बाहरी दूरी, से दूरी {{math|''f''(''x'')}} को {{math|''f''(''y'')}} में {{mvar|T}}. जोड़ी का खिंचाव कारक इन दो दूरियों के बीच का अनुपात है, {{math|''d''(''f''(''x''),''f''(''y''))/''d''(''x'',''y'')}}. संपूर्ण मानचित्रण का खिंचाव कारक सभी बिंदुओं के जोड़े के खिंचाव कारकों में सर्वोच्च है। खिंचाव कारक को विकृति भी कहा गया है{{Disputed inline|Terminology: distortion|date=June 2022}} या मैपिंग का फैलाव।


[[ज्यामितीय स्पैनर]], [[भारित ग्राफ]]के सिद्धांत में खिंचाव कारक महत्वपूर्ण है जो [[यूक्लिडियन विमान]] में बिंदुओं के एक सेट के बीच [[यूक्लिडियन दूरी]] का अनुमान लगाता है। इस मामले में, एम्बेडेड मीट्रिक {{mvar|S}} एक परिमित मीट्रिक स्थान है, जिसकी दूरियाँ ग्राफ़ में सबसे छोटी पथ समस्या और मीट्रिक हैं {{mvar|T}} जिसके अंदर {{mvar|S}} यूक्लिडियन तल अंतर्निहित है। जब ग्राफ़ और उसकी एम्बेडिंग तय हो जाती है, लेकिन ग्राफ़ के किनारे का वजन अलग-अलग हो सकता है, तो खिंचाव कारक तब कम हो जाता है जब वजन बिल्कुल किनारे के अंतिम बिंदुओं के बीच यूक्लिडियन दूरी के बराबर होता है। इस क्षेत्र में अनुसंधान ने किसी दिए गए बिंदु सेट के लिए [[विरल ग्राफ]]़ खोजने पर ध्यान केंद्रित किया है जिनमें कम खिंचाव कारक है।<ref>{{citation|first1=Giri|last1=Narasimhan|first2=Michiel|last2=Smid|title=Geometric Spanner Networks|publisher=[[Cambridge University Press]]|year=2007|isbn=0-521-81513-4}}.</ref>
{{distinguish|text=[[छद्म-एनोसोव मानचित्र]] का खिंचाव कारक}}
जॉनसन-लिंडेनस्ट्रॉस लेम्मा का दावा है कि किसी भी परिमित सेट के साथ {{mvar|n}} यूक्लिडियन स्पेस में बिंदुओं को आयाम के यूक्लिडियन स्पेस में एम्बेड किया जा सकता है {{math|''O''(log&nbsp;''n'')}} विकृति के साथ {{math|1 + ''&epsilon;''}}, किसी भी स्थिरांक के लिए {{math|''&epsilon;'' > 0}}, जहां स्थिर कारक है {{mvar|O}}-नोटेशन की पसंद पर निर्भर करता है{{mvar|&epsilon;}}.<ref>{{citation
[[एम्बेडिंग|अंत: स्थापन]] का वृद्धि गुणक (अर्थात, लिप्सचिट्ज़ निरंतरता) उस कारक को मापता है जिसके द्वारा अंत: स्थापन दूरियों को विकृत करता है। मान लीजिए कि [[मीट्रिक स्थान]] {{mvar|S}} किसी अन्य मीट्रिक स्थान में सन्निहित है {{mvar|T}} [[मीट्रिक मानचित्र|मीटरी प्रतिचित्रण]] द्वारा, सतत एकैक फलन  {{mvar|f}}  जो प्रत्येक युम्म बिंदुओं के बीच की दूरी को संरक्षित या कम करता है। फिर अंत: स्थापन {{mvar|S}} में बिंदुओं के युम्म के बीच की दूरी की दो अलग-अलग धारणाओं को उदित करती है। {{mvar|S}} में बिंदु {{math|(''x'',''y'')}} की किसी भी युम्म में [[आंतरिक मीट्रिक|आंतरिक दूरी]], {{mvar|S}} में {{mvar|x}} से {{mvar|y}} की दूरी और छोटी बाहरी दूरी {{mvar|T}} में {{math|''f''(''x'')}} से ({{math|''f''(''y'')}} तक की दूरी दोनों होती है।  युम्म का वृद्धि गुणक इन दो दूरियों {{math|''d''(''f''(''x''),''f''(''y''))/''d''(''x'',''y'')}} के बीच का अनुपात है। संपूर्ण मानचित्रण का वृद्धि गुणक सभी बिंदुओं के युम्म के वृद्धि गुणक में सर्वोच्च है। वृद्धि गुणक को विरूपण या विस्फारण भी कहा गया है।
 
[[ज्यामितीय स्पैनर]], [[भारित ग्राफ]] के सिद्धांत में वृद्धि गुणक महत्वपूर्ण है जो [[यूक्लिडियन विमान|यूक्लिडियन समतल]] में बिंदुओं के समुच्चय के बीच [[यूक्लिडियन दूरी]] का अनुमान लगाता है। इस स्थिति में, सन्निहित मीट्रिक {{mvar|S}} परिमित मीट्रिक स्थान है, जिसकी दूरी ग्राफ़ में सबसे छोटी पथ लंबाई है, और मीट्रिक {{mvar|T}} जिसमें {{mvar|S}} अंतर्निहित है वह यूक्लिडियन समष्टि है। ग्राफ़ और उसकी अंत: स्थापन तय हो जाती है, लेकिन ग्राफ़ के किनारे का वजन अलग-अलग हो सकता है, तो वृद्धि गुणक कम हो जाता है जब वजन बिल्कुल किनारे के अंतिम बिंदुओं के बीच यूक्लिडियन दूरी के बराबर होता है। इस क्षेत्र में अनुसंधान ने किसी दिए गए बिंदु समुच्चय के लिए [[विरल ग्राफ]]निष्कर्ष पर ध्यान केंद्रित किया है जिनमें कम वृद्धि गुणक है।<ref>{{citation|first1=Giri|last1=Narasimhan|first2=Michiel|last2=Smid|title=Geometric Spanner Networks|publisher=[[Cambridge University Press]]|year=2007|isbn=0-521-81513-4}}.</ref>
 
जॉनसन-लिंडेनस्ट्रॉस लेम्मा का दावा है कि किसी भी यूक्लिडियन समष्टि में {{mvar|n}} बिंदुओं के साथ किसी भी परिमित समुच्चय को विरूपण {{math|1 + ''&epsilon;''}} के साथ आयाम {{math|''O''(log&nbsp;''n'')}} के यूक्लिडियन समष्टि में सन्निहित किया जा सकता है, किसी भी स्थिरांक {{math|''&epsilon;'' > 0}} के लिए, जहां निरंतर कारक {{mvar|O}}-नोटेशन {{mvar|&epsilon;}} की विकल्प पर निर्भर करता है।<ref>{{citation
  | last1 = Johnson
  | last1 = Johnson
  | first1 = William B.
  | first1 = William B.
Line 35: Line 36:
  | url-access = registration
  | url-access = registration
  | url = https://archive.org/details/conferenceinmode0000conf/page/189
  | url = https://archive.org/details/conferenceinmode0000conf/page/189
  }}.</ref> यह परिणाम, और कम-विरूपण मीट्रिक एम्बेडिंग के निर्माण के संबंधित तरीके, सन्निकटन एल्गोरिदम के सिद्धांत में महत्वपूर्ण हैं। इस क्षेत्र में एक प्रमुख खुली समस्या [[जीएनआरएस अनुमान]] है, जो (यदि सत्य है) उन ग्राफ़ों के परिवारों की विशेषता बताएगी जिनमें सीमाबद्ध-खिंचाव एम्बेडिंग है <math>\ell_1</math> सभी लघु-बंद ग्राफ़ परिवारों के रूप में रिक्त स्थान।
  }}.</ref> यह परिणाम, और कम-विरूपण मीट्रिक अंत: स्थापन के निर्माण के संबंधित तरीके, सन्निकटन कलन विधि के सिद्धांत में महत्वपूर्ण हैं। इस क्षेत्र में प्रमुख अनिर्णित समस्या [[जीएनआरएस अनुमान]] है, जो (यदि सत्य है) उन ग्राफ़ों के वर्ग की विशेषता बताएगी जिनमें सीमाबद्ध-वृद्धि अंत: स्थापन है <math>\ell_1</math>सभी लघु-संकीर्ण ग्राफ़ वर्ग के रूप में रिक्त स्थान है।


गाँठ सिद्धांत में, गाँठ की विकृति एक [[गाँठ अपरिवर्तनीय]] है, यूक्लिडियन अंतरिक्ष में एक [[अंतरिक्ष वक्र]] के रूप में गाँठ के किसी भी एम्बेडिंग का न्यूनतम खिंचाव कारक है।
नॉट सिद्धांत में, नॉट की विरूपण [[गाँठ अपरिवर्तनीय|नॉट अपरिवर्तनीय]] है, यूक्लिडियन समष्टि में [[अंतरिक्ष वक्र|समष्टि वक्र]] के रूप में नॉट के किसी भी अंत: स्थापन का न्यूनतम वृद्धि गुणक है। स्नातक शोधकर्ता जॉन पार्डन ने अपने शोध के लिए 2012 [[मॉर्गन पुरस्कार]] जीता, जिसमें दिखाया गया कि टोरस नॉट की विरूपण पर कोई ऊपरी सीमा नहीं है, जो मूल रूप से [[मिखाइल लियोनिदोविच ग्रोमोव]] द्वारा प्रस्तुत समस्या को हल करता है।<ref>{{citation|title=2012 Morgan Prize|journal=[[Notices of the American Mathematical Society]]|date=April 2012|doi=10.1090/noti825|pages=569–571|volume=59|issue=4|first=Elaine|last=Kehoe|doi-access=free}}.</ref><ref>{{citation
स्नातक शोधकर्ता जॉन पार्डन ने अपने शोध के लिए 2012 [[मॉर्गन पुरस्कार]] जीता, जिसमें दिखाया गया कि टोरस गांठों की विकृति पर कोई ऊपरी सीमा नहीं है, जो मूल रूप से [[मिखाइल लियोनिदोविच ग्रोमोव]] द्वारा प्रस्तुत समस्या को हल करता है।<ref>{{citation|title=2012 Morgan Prize|journal=[[Notices of the American Mathematical Society]]|date=April 2012|doi=10.1090/noti825|pages=569–571|volume=59|issue=4|first=Elaine|last=Kehoe|doi-access=free}}.</ref><ref>{{citation
  | last = Pardon | first = John
  | last = Pardon | first = John
  | doi = 10.4007/annals.2011.174.1.21
  | doi = 10.4007/annals.2011.174.1.21
Line 49: Line 49:
  | arxiv = 1010.1972| volume = 174
  | arxiv = 1010.1972| volume = 174
  | year = 2011}}.</ref>
  | year = 2011}}.</ref>
[[वक्र-छोटा प्रवाह]] के अध्ययन में, जिसमें यूक्लिडियन विमान में वक्र का प्रत्येक बिंदु स्थानीय वक्रता के आनुपातिक गति के साथ, वक्र के लंबवत चलता है, {{harvtxt|Huisken|1998}} साबित हुआ कि किसी भी सरल बंद चिकने वक्र का खिंचाव कारक (चाप की लंबाई द्वारा मापी गई आंतरिक दूरी के साथ) एकरस रूप से बदलता है। अधिक विशेष रूप से, प्रत्येक जोड़ी पर {{math|(''x'',''y'')}} जो खिंचाव कारक का एक स्थानीय अधिकतम बनाता है, खिंचाव कारक सख्ती से घट रहा है, सिवाय इसके कि जब वक्र एक वृत्त हो। इस संपत्ति का उपयोग बाद में गेज-हैमिल्टन-ग्रेसन प्रमेय के प्रमाण को सरल बनाने के लिए किया गया था, जिसके अनुसार प्रत्येक सरल बंद चिकना वक्र तब तक सरल और चिकना रहता है जब तक कि वह एक बिंदु पर ढह न जाए, ऐसा करने से पहले एक वृत्त के आकार में परिवर्तित हो जाता है।<ref>{{citation
 
[[वक्र-छोटा प्रवाह|वक्र-लघुता प्रवाह]] के अध्ययन में, जिसमें यूक्लिडियन समतल में वक्र का प्रत्येक बिंदु स्थानीय वक्रता के आनुपातिक गति के साथ, वक्र के लंबवत चलता है, {{harvtxt|हुइस्केन|1998}} ने सिद्ध किया कि किसी भी सहज संकीर्ण सिनग्ध वक्र का वृद्धि गुणक (चाप की लंबाई द्वारा मापी गई आंतरिक दूरी के साथ) एकरस रूप से बदलता है। अधिक विशेष रूप से, प्रत्येक युम्म {{math|(''x'',''y'')}} पर जो वृद्धि गुणक का स्थानीय अधिकतम बनाता है, सिवाय इसके कि जब वक्र एक वृत्त हो वृद्धि गुणक सख्ती से घट रहा है। इस गुण का उपयोग बाद में गेज-हैमिल्टन-ग्रेसन प्रमेय के प्रमाण को सहज बनाने के लिए किया गया था, जिसके अनुसार प्रत्येक सहज संकीर्ण सिनग्ध वक्र तब तक सहज और सिनग्ध रहता है जब तक कि वह बिंदु पर संचय न जाए, ऐसा करने से पहले वृत्त के आकार में परिवर्तित हो जाता है।<ref>{{citation
  | last = Huisken | first = Gerhard | authorlink = Gerhard Huisken
  | last = Huisken | first = Gerhard | authorlink = Gerhard Huisken
  | issue = 1
  | issue = 1
Line 70: Line 71:
  | volume = 653
  | volume = 653
  | year = 2011}}.</ref>
  | year = 2011}}.</ref>
==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}

Revision as of 11:27, 9 July 2023

अंत: स्थापन का वृद्धि गुणक (अर्थात, लिप्सचिट्ज़ निरंतरता) उस कारक को मापता है जिसके द्वारा अंत: स्थापन दूरियों को विकृत करता है। मान लीजिए कि मीट्रिक स्थान S किसी अन्य मीट्रिक स्थान में सन्निहित है T मीटरी प्रतिचित्रण द्वारा, सतत एकैक फलन f जो प्रत्येक युम्म बिंदुओं के बीच की दूरी को संरक्षित या कम करता है। फिर अंत: स्थापन S में बिंदुओं के युम्म के बीच की दूरी की दो अलग-अलग धारणाओं को उदित करती है। S में बिंदु (x,y) की किसी भी युम्म में आंतरिक दूरी, S में x से y की दूरी और छोटी बाहरी दूरी T में f(x) से (f(y) तक की दूरी दोनों होती है। युम्म का वृद्धि गुणक इन दो दूरियों d(f(x),f(y))/d(x,y) के बीच का अनुपात है। संपूर्ण मानचित्रण का वृद्धि गुणक सभी बिंदुओं के युम्म के वृद्धि गुणक में सर्वोच्च है। वृद्धि गुणक को विरूपण या विस्फारण भी कहा गया है।

ज्यामितीय स्पैनर, भारित ग्राफ के सिद्धांत में वृद्धि गुणक महत्वपूर्ण है जो यूक्लिडियन समतल में बिंदुओं के समुच्चय के बीच यूक्लिडियन दूरी का अनुमान लगाता है। इस स्थिति में, सन्निहित मीट्रिक S परिमित मीट्रिक स्थान है, जिसकी दूरी ग्राफ़ में सबसे छोटी पथ लंबाई है, और मीट्रिक T जिसमें S अंतर्निहित है वह यूक्लिडियन समष्टि है। ग्राफ़ और उसकी अंत: स्थापन तय हो जाती है, लेकिन ग्राफ़ के किनारे का वजन अलग-अलग हो सकता है, तो वृद्धि गुणक कम हो जाता है जब वजन बिल्कुल किनारे के अंतिम बिंदुओं के बीच यूक्लिडियन दूरी के बराबर होता है। इस क्षेत्र में अनुसंधान ने किसी दिए गए बिंदु समुच्चय के लिए विरल ग्राफनिष्कर्ष पर ध्यान केंद्रित किया है जिनमें कम वृद्धि गुणक है।[1]

जॉनसन-लिंडेनस्ट्रॉस लेम्मा का दावा है कि किसी भी यूक्लिडियन समष्टि में n बिंदुओं के साथ किसी भी परिमित समुच्चय को विरूपण 1 + ε के साथ आयाम O(log n) के यूक्लिडियन समष्टि में सन्निहित किया जा सकता है, किसी भी स्थिरांक ε > 0 के लिए, जहां निरंतर कारक O-नोटेशन ε की विकल्प पर निर्भर करता है।[2] यह परिणाम, और कम-विरूपण मीट्रिक अंत: स्थापन के निर्माण के संबंधित तरीके, सन्निकटन कलन विधि के सिद्धांत में महत्वपूर्ण हैं। इस क्षेत्र में प्रमुख अनिर्णित समस्या जीएनआरएस अनुमान है, जो (यदि सत्य है) उन ग्राफ़ों के वर्ग की विशेषता बताएगी जिनमें सीमाबद्ध-वृद्धि अंत: स्थापन है सभी लघु-संकीर्ण ग्राफ़ वर्ग के रूप में रिक्त स्थान है।

नॉट सिद्धांत में, नॉट की विरूपण नॉट अपरिवर्तनीय है, यूक्लिडियन समष्टि में समष्टि वक्र के रूप में नॉट के किसी भी अंत: स्थापन का न्यूनतम वृद्धि गुणक है। स्नातक शोधकर्ता जॉन पार्डन ने अपने शोध के लिए 2012 मॉर्गन पुरस्कार जीता, जिसमें दिखाया गया कि टोरस नॉट की विरूपण पर कोई ऊपरी सीमा नहीं है, जो मूल रूप से मिखाइल लियोनिदोविच ग्रोमोव द्वारा प्रस्तुत समस्या को हल करता है।[3][4]

वक्र-लघुता प्रवाह के अध्ययन में, जिसमें यूक्लिडियन समतल में वक्र का प्रत्येक बिंदु स्थानीय वक्रता के आनुपातिक गति के साथ, वक्र के लंबवत चलता है, हुइस्केन (1998) ने सिद्ध किया कि किसी भी सहज संकीर्ण सिनग्ध वक्र का वृद्धि गुणक (चाप की लंबाई द्वारा मापी गई आंतरिक दूरी के साथ) एकरस रूप से बदलता है। अधिक विशेष रूप से, प्रत्येक युम्म (x,y) पर जो वृद्धि गुणक का स्थानीय अधिकतम बनाता है, सिवाय इसके कि जब वक्र एक वृत्त हो वृद्धि गुणक सख्ती से घट रहा है। इस गुण का उपयोग बाद में गेज-हैमिल्टन-ग्रेसन प्रमेय के प्रमाण को सहज बनाने के लिए किया गया था, जिसके अनुसार प्रत्येक सहज संकीर्ण सिनग्ध वक्र तब तक सहज और सिनग्ध रहता है जब तक कि वह बिंदु पर संचय न जाए, ऐसा करने से पहले वृत्त के आकार में परिवर्तित हो जाता है।[5][6]

संदर्भ

  1. Narasimhan, Giri; Smid, Michiel (2007), Geometric Spanner Networks, Cambridge University Press, ISBN 0-521-81513-4.
  2. Johnson, William B.; Lindenstrauss, Joram (1984), "Extensions of Lipschitz mappings into a Hilbert space", in Beals, Richard; Beck, Anatole; Bellow, Alexandra; et al. (eds.), Conference in modern analysis and probability (New Haven, Conn., 1982), Contemporary Mathematics, vol. 26, Providence, RI: American Mathematical Society, pp. 189–206, doi:10.1090/conm/026/737400, ISBN 0-8218-5030-X, MR 0737400.
  3. Kehoe, Elaine (April 2012), "2012 Morgan Prize", Notices of the American Mathematical Society, 59 (4): 569–571, doi:10.1090/noti825.
  4. Pardon, John (2011), "On the distortion of knots on embedded surfaces", Annals of Mathematics, Second Series, 174 (1): 637–646, arXiv:1010.1972, doi:10.4007/annals.2011.174.1.21, MR 2811613.
  5. Huisken, Gerhard (1998), "A distance comparison principle for evolving curves", The Asian Journal of Mathematics, 2 (1): 127–133, hdl:11858/00-001M-0000-0013-5964-4, MR 1656553.
  6. Andrews, Ben; Bryan, Paul (2011), "Curvature bound for curve shortening flow via distance comparison and a direct proof of Grayson's theorem", Journal für die Reine und Angewandte Mathematik, 653: 179–187, arXiv:0908.2682, doi:10.1515/CRELLE.2011.026, MR 2794630.