थ्रैकल: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(13 intermediate revisions by 3 users not shown)
Line 1: Line 1:
एक '''थ्रैकल''' तल में एक [[ग्राफ (असतत गणित)|ग्राफ]] का एक [[अंतःस्थापन]] ([[एम्बेडिंग]]) है, जैसे कि प्रत्येक किनारा एक [[जॉर्डन चाप]] है और और किनारों का हर युग्म बिल्कुल एक बार मिलता है। किनारे या तो एक सामान्य अंत बिंदु पर मिल सकते हैं, या, यदि उनके पास कोई अंत बिंदु नहीं है, तो उनके आंतरिक भाग में एक बिंदु पर मिल सकते हैं। बाद की स्थिति में, क्रॉसिंग ''[[अनुप्रस्थ]]'' होना चाहिए।<ref name="lps">{{citation |first1=L. |last1=Lovász |authorlink1=László Lovász |first2=J. |last2=Pach |author2-link=János Pach |first3=M. |last3=Szegedy |authorlink3=Mario Szegedy |title=On Conway's thrackle conjecture |journal=[[Discrete and Computational Geometry]] |volume=18 |year=1997 |pages=369–376 |doi=10.1007/PL00009322 |mr=1476318 |issue=4|doi-access=free }}. A preliminary version of these results was reviewed in {{citation |first=J. |last=O'Rourke |author-link=Joseph O'Rourke (professor) |title=Computational geometry column 26 |journal=ACM SIGACT News |volume=26 |issue=2 |year=1995 |pages=15–17 |doi=10.1145/202840.202842|arxiv=cs/9908007 }}.</ref>
एक '''थ्रैकल''' तल में एक [[ग्राफ (असतत गणित)|ग्राफ]] का एक [[अंतःस्थापन]] ([[एम्बेडिंग]]) है, जैसे कि प्रत्येक किनारा एक [[जॉर्डन चाप]] है और और किनारों का हर युग्म ठीक एक बार मिलता है। किनारे या तो एक सामान्य अंत बिंदु पर मिल सकते हैं, या, यदि उनके पास कोई अंत बिंदु नहीं है, तो उनके आंतरिक भाग में एक बिंदु पर मिल सकते हैं। बाद की स्थिति में, क्रॉसिंग ''[[अनुप्रस्थ]]'' होना चाहिए।<ref name="lps">{{citation |first1=L. |last1=Lovász |authorlink1=László Lovász |first2=J. |last2=Pach |author2-link=János Pach |first3=M. |last3=Szegedy |authorlink3=Mario Szegedy |title=On Conway's thrackle conjecture |journal=[[Discrete and Computational Geometry]] |volume=18 |year=1997 |pages=369–376 |doi=10.1007/PL00009322 |mr=1476318 |issue=4|doi-access=free }}. A preliminary version of these results was reviewed in {{citation |first=J. |last=O'Rourke |author-link=Joseph O'Rourke (professor) |title=Computational geometry column 26 |journal=ACM SIGACT News |volume=26 |issue=2 |year=1995 |pages=15–17 |doi=10.1145/202840.202842|arxiv=cs/9908007 }}.</ref>




== रैखिक थ्रैकल्स ==
== रैखिक थ्रैकल्स ==
[[File:Reinhardt 15-gons.svg|thumb|चार [[रेनहार्ड्ट बहुभुज]]। उनके व्यास (नीला) रैखिक थ्रैकल्स बनाते हैं।]]एक रैखिक थ्रैकल इस तरह से खींचा गया थ्रैकल है कि इसके किनारे सीधी रेखा खंड हैं। जैसा कि पॉल एर्डोस ने देखा, प्रत्येक रैखिक थ्रैकल में अधिक से अधिक किनारों के रूप में कोने होते हैं। यदि एक शीर्ष ''v'' तीन या अधिक किनारों ''vw'', ''vx'', और ''vy'' से जुड़ा है, तो उन किनारों में से कम से कम एक किनारा ("vw" कहें) पर स्थित है एक रेखा जो दो अन्य किनारों को अलग करती है। फिर, ''w'' के पास डिग्री (ग्राफ़ थ्योरी) एक होनी चाहिए, क्योंकि ''vw'' के अलावा ''w'' पर समाप्त होने वाला कोई भी रेखा खंड, ''vx'' और ''vy'' दोनों को नहीं छू सकता है। . ''w'' और ''vw'' को हटाने से किनारों और शीर्षों की संख्या के बीच के अंतर को बदले बिना एक छोटा थ्रैकल पैदा होता है। इस तरह से हटाने के बाद एक थ्रैकल होता है जिसमें प्रत्येक शीर्ष पर अधिकतम दो पड़ोसी होते हैं, [[ हाथ मिलाना लेम्मा ]] द्वारा किनारों की संख्या अधिक से अधिक वर्टिकल की संख्या होती है।<ref name="e46">{{citation|author-link=Paul Erdős|first=P.|last=Erdős|title=On sets of distances of ''n'' points|journal=[[American Mathematical Monthly]]|volume=53|year=1946|issue=5|pages=248–250|url=http://www.renyi.hu/~p_erdos/1946-03.pdf|doi=10.2307/2305092|jstor=2305092}}.</ref> एर्दोस के प्रमाण के आधार पर, कोई भी अनुमान लगा सकता है कि प्रत्येक रैखिक थ्रैकल एक [[seudoforest]] है। विषम लंबाई के प्रत्येक चक्र को एक रेखीय थ्रैकल बनाने के लिए व्यवस्थित किया जा सकता है, लेकिन यह समान-लंबाई वाले चक्र के लिए संभव नहीं है, क्योंकि यदि चक्र के एक किनारे को मनमाने ढंग से चुना जाता है, तो दूसरे चक्र के कोने बारी-बारी से रेखा के विपरीत दिशा में स्थित होने चाहिए। इस किनारे के माध्यम से।
[[File:Reinhardt 15-gons.svg|thumb|चार [[रेनहार्ड्ट बहुभुज]]। उनके व्यास (नीला) रैखिक थ्रैकल्स बनाते हैं।]]एक '''रैखिक थ्रैकल''' इस तरह से खींचा गया थ्रैकल है कि इसके किनारे सीधी रेखा खंड हैं। जैसा कि [[पॉल एर्डोस]] ने देखा, प्रत्येक रैखिक थ्रैकल में अधिक से अधिक किनारों के रूप में शीर्ष होते हैं। यदि एक शीर्ष ''v'' तीन या अधिक किनारों ''vw'', ''vx'', और ''vy'' से जुड़ा है, तो उन किनारों में से कम से कम एक किनारा (जैसे vw ) एक रेखा पर स्थित है जो दो अन्य किनारों को अलग करता है। फिर, ''w'' की [[कोटि]] एक होनी चाहिए, क्योंकि ''vw'' के अलावा ''w'' पर समाप्त होने वाला कोई भी रेखा खंड, ''vx'' और ''vy'' दोनों को नहीं स्पर्श सकता है। किनारों और शीर्षों की संख्या के बीच के अंतर को परिवर्तन किए बिना ''w'' और ''vw'' को हटाने से एक छोटे थ्रैकल की उत्पत्ति होती है। इस तरह से हटाने के बाद एक थ्रैकल होता है जिसमें प्रत्येक शीर्ष पर अधिकतम दो सहवासी होते हैं, [[ हाथ मिलाना लेम्मा | हैंडशेकिंग लेम्मा]] द्वारा किनारों की संख्या अधिक से अधिक शीर्षों की संख्या होती है।<ref name="e46">{{citation|author-link=Paul Erdős|first=P.|last=Erdős|title=On sets of distances of ''n'' points|journal=[[American Mathematical Monthly]]|volume=53|year=1946|issue=5|pages=248–250|url=http://www.renyi.hu/~p_erdos/1946-03.pdf|doi=10.2307/2305092|jstor=2305092}}.</ref> एर्डोस के प्रमाण के आधार पर, कोई भी अनुमान लगा सकता है कि प्रत्येक रैखिक थ्रैकल एक [[seudoforest|स्यूडोफ़ॉरेस्ट]] है। विषम लंबाई के प्रत्येक चक्र को एक रेखीय थ्रैकल बनाने के लिए व्यवस्थित किया जा सकता है, लेकिन यह सम-लंबाई वाले चक्र के लिए संभव नहीं है, क्योंकि यदि चक्र के एक किनारे को स्वेच्छतः से चुना जाता है, तो चक्र के अन्य शीर्षों को बारी-बारी से इस किनारे के माध्यम से रेखा की विपरीत दिशा में स्थित होना चाहिए।


[[मीका मोती]] ने एक और सरल प्रमाण प्रदान किया कि रैखिक थ्रैकल्स में अधिकांश n किनारे होते हैं, इस तथ्य के आधार पर कि एक रेखीय थ्रैकल में प्रत्येक किनारे का एक समापन बिंदु होता है, जिस पर किनारे अधिकतम 180 ° के कोण पर फैले होते हैं, और जिसके लिए यह सबसे अधिक दक्षिणावर्त होता है। इस अवधि के भीतर बढ़त। इसके लिए, यदि नहीं, तो दो किनारे होंगे, किनारे के विपरीत छोरों के लिए घटना और किनारे के माध्यम से रेखा के विपरीत किनारों पर झूठ बोलना, जो एक दूसरे को पार नहीं कर सके। लेकिन प्रत्येक शीर्ष में केवल एक किनारे के संबंध में यह गुण हो सकता है, इसलिए किनारों की संख्या अधिक से अधिक वर्टिकल की संख्या के बराबर होती है।<ref name="pach"/>
[[मीका मोती|मीका पर्ल्स]] ने एक और सरल प्रमाण प्रदान किया कि रैखिक थ्रैकल्स में अधिकांश ''n'' किनारे होते हैं, इस तथ्य के आधार पर कि एक रेखीय थ्रैकल में प्रत्येक किनारे का एक अंत बिंदु होता है, जिस पर किनारे अधिकतम 180 ° के कोण पर विस्तृति होते हैं, और जिसके लिए यह इस सीमा (स्पैन) के अंदर सबसे अधिक दक्षिणावर्त किनारा होता है। इसके लिए, यदि नहीं, तो दो किनारे होंगे, किनारे के विपरीत अंत बिदुओं के लिए घटना और किनारे के माध्यम से रेखा की विपरीत किनारों पर लाइंग होना, जो एक दूसरे को क्रॉस नहीं कर सके है। लेकिन प्रत्येक शीर्ष में केवल एक किनारे के संबंध में यह गुण हो सकता है, इसलिए किनारों की संख्या अधिक से अधिक शीर्षों की संख्या के बराबर होती है।<ref name="pach"/>


जैसा कि एर्दोस ने भी देखा, बिंदु सेट के [[व्यास]] को महसूस करने वाले बिंदुओं के जोड़े के सेट को एक रैखिक थ्रैकल बनाना चाहिए: कोई भी दो व्यास एक दूसरे से अलग नहीं हो सकते हैं, क्योंकि यदि वे थे तो उनके चार समापन बिंदु अलग-अलग दूरी पर एक जोड़ी होगी दो अलग-अलग किनारों की तुलना में। इस कारण से, तल में n बिंदुओं के प्रत्येक सेट में अधिक से अधिक n व्यास जोड़े हो सकते हैं, जो [[हेंज हॉफ]] और [[एरिका पन्नविट्ज़]] द्वारा 1934 में पूछे गए एक प्रश्न का उत्तर देते हैं।<ref>{{citation
जैसा कि एर्डोस ने भी देखा, बिंदु समुच्चय के [[व्यास]] को प्राप्त करने वाले बिंदुओं के युग्मों के समुच्चय को एक रैखिक थ्रैकल बनाना चाहिए: कोई भी दो व्यासों को एक दूसरे से अलग नहीं किया जा सकता है, क्योंकि यदि वे होते तो उनके चार अंतबिंदुओं में दो असंयुक्त किनारों के अलावा दूर की दूरी पर एक युग्म होता है। इस कारण से, तल में ''n'' बिंदुओं के प्रत्येक समुच्चय में अधिक से अधिक ''n'' व्यास युग्म हो सकते हैं, जो [[हेंज हॉफ]] और [[एरिका पन्नविट्ज़]] द्वारा 1934 में पूछे गए एक प्रश्न का उत्तर देते हैं।<ref>{{citation
  | last1 = Hopf | first1 = H. | author1-link = Heinz Hopf
  | last1 = Hopf | first1 = H. | author1-link = Heinz Hopf
  | last2 = Pannwitz | first2 = E. | author2-link = Erika Pannwitz
  | last2 = Pannwitz | first2 = E. | author2-link = Erika Pannwitz
Line 14: Line 14:
  | title = Aufgabe Nr. 167
  | title = Aufgabe Nr. 167
  | volume = 43
  | volume = 43
  | year = 1934}}.</ref> एंड्रयू वाज़सोनी ने इस समस्या को सामान्य करते हुए, उच्च आयामों में व्यास जोड़े की संख्या पर अनुमान लगाया।<ref name="e46"/>
  | year = 1934}}.</ref> एंड्रयू वाज़सोनी ने इस समस्या को सामान्य करते हुए, उच्च आयामों में व्यास युग्मों की संख्या पर अनुमान लगाया था।<ref name="e46"/>
 
[[कम्प्यूटेशनल ज्यामिति|अभिकलनी ज्यामिति]] में, [[घूर्णन कैलीपर्स]] की विधि का उपयोग [[उत्तल स्थिति|अवमुख स्थिति]] में बिंदुओं के किसी भी समुच्चय से एक रैखिक थ्रैकल बनाने के लिए किया जा सकता है, बिंदुओं के युग्मों को जोड़कर जो बिंदुओं के [[अवमुख हल]] को समानांतर रेखाओं का समर्थन करते हैं।<ref>{{citation|url=https://www.ics.uci.edu/~eppstein/junkyard/rcg.html|first=David|last=Eppstein|author-link=David Eppstein|title=The Rotating Caliper Graph|work=The Geometry Junkyard|date=May 1995}}</ref> इस ग्राफ में व्यास युग्मों के थ्रैकल को उपग्राफ के रूप में सम्मिलित किया गया है।<ref>For the fact that the rotating caliper graph contains all diameter pairs, see {{citation|url = http://euro.ecom.cmu.edu/people/faculty/mshamos/1978ShamosThesis.pdf|title = Computational Geometry|date = 1978|publisher = Yale University|last = Shamos|first = Michael|author-link = Michael Shamos|series=Doctoral dissertation}}. For the fact that the diameter pairs form a thrackle, see, e.g., {{harvtxt|Pach|Sterling|2011}}.</ref>
 
[[रेनहार्ड्ट बहुभुजों]] के व्यास रैखिक थ्रैकल बनाते हैं। सबसे [[बड़ी छोटी बहुभुज]] समस्या को हल करने के लिए रैखिक थ्रैकल्स की गणना का उपयोग किया जा सकता है, इसके व्यास के सापेक्ष अधिकतम क्षेत्र के साथ ''n-गॉन'' खोजने के लिए किया जा सकता है।<ref name="Graham">{{citation|last=Graham|first=R. L.|author-link=Ronald Graham|title=The largest small hexagon|journal=[[Journal of Combinatorial Theory]]|series=Series A|volume=18|pages=165–170|year=1975|issue=2|url=http://www.math.ucsd.edu/~ronspubs/75_02_hexagon.pdf|doi=10.1016/0097-3165(75)90004-7|doi-access=free}}.</ref>


[[कम्प्यूटेशनल ज्यामिति]] में, कैलीपर्स को घुमाने की विधि का उपयोग [[उत्तल स्थिति]] में बिंदुओं के किसी भी सेट से एक रैखिक थ्रैकल बनाने के लिए किया जा सकता है, बिंदुओं के जोड़े को जोड़कर जो बिंदुओं के उत्तल हल को समानांतर रेखाओं का समर्थन करते हैं।<ref>{{citation|url=https://www.ics.uci.edu/~eppstein/junkyard/rcg.html|first=David|last=Eppstein|author-link=David Eppstein|title=The Rotating Caliper Graph|work=The Geometry Junkyard|date=May 1995}}</ref> इस ग्राफ में व्यास जोड़े के थ्रैकल को सबग्राफ के रूप में शामिल किया गया है।<ref>For the fact that the rotating caliper graph contains all diameter pairs, see {{citation|url = http://euro.ecom.cmu.edu/people/faculty/mshamos/1978ShamosThesis.pdf|title = Computational Geometry|date = 1978|publisher = Yale University|last = Shamos|first = Michael|author-link = Michael Shamos|series=Doctoral dissertation}}. For the fact that the diameter pairs form a thrackle, see, e.g., {{harvtxt|Pach|Sterling|2011}}.</ref>
रेनहार्ड्ट बहुभुजों के व्यास रैखिक थ्रैकल बनाते हैं। सबसे बड़ी छोटी बहुभुज समस्या को हल करने के लिए रैखिक थ्रैकल्स की गणना का उपयोग किया जा सकता है, इसके व्यास के सापेक्ष अधिकतम क्षेत्र के साथ एन-गॉन खोजने के लिए।<ref name="Graham">{{citation|last=Graham|first=R. L.|author-link=Ronald Graham|title=The largest small hexagon|journal=[[Journal of Combinatorial Theory]]|series=Series A|volume=18|pages=165–170|year=1975|issue=2|url=http://www.math.ucsd.edu/~ronspubs/75_02_hexagon.pdf|doi=10.1016/0097-3165(75)90004-7|doi-access=free}}.</ref>




== थ्रैकल अनुमान ==
== थ्रैकल अनुमान ==
{{unsolved|mathematics|Can a thrackle have more edges than vertices?}}
{{unsolved|mathematics|Can a thrackle have more edges than vertices?}}
[[Image:6-cycle thrackle.png|thumb|6-चक्र ग्राफ का एक थ्रैकल एम्बेडिंग।]]जॉन हॉर्टन कॉनवे|जॉन एच. कॉनवे ने अनुमान लगाया कि, किसी भी थ्रैकल में, किनारों की संख्या अधिक से अधिक शीर्षों की संख्या के बराबर होती है। कॉनवे ने खुद शब्दावली पथ और स्पॉट (क्रमशः किनारों और कोने के लिए) का इस्तेमाल किया, इसलिए 'कॉनवे का थ्रैकल अनुमान' मूल रूप से कहा गया था
[[Image:6-cycle thrackle.png|thumb|6-चक्र ग्राफ का एक थ्रैकल अंत:स्थापन।]][[जॉन एच. कॉनवे]] ने अनुमान लगाया कि, किसी भी थ्रैकल में किनारों की संख्या अधिक से अधिक शीर्षों की संख्या के बराबर होती है। कॉनवे ने स्वयं शब्दावली (टर्मिनोलॉजी)  ''पथ'' और ''स्पॉट'' (क्रमशः ''किनारों'' और ''शीर्षों'' के लिए) का उपयोग किया, इसलिए '''कॉनवे के थ्रैकल अनुमान''' को  मूल रूप से कहा गया था कि ''हर थ्रैकल में पथ के रूप में कम से कम कई स्पॉट हैं''। कॉनवे ने इस अनुमान को सिद्ध करने या असत्य सिद्ध करने के लिए $ 1000 पुरस्कार का प्रस्ताव रखा, जिसमें [[कॉनवे की 99-ग्राफ की समस्या]], [[डेनजर समुच्चय]] का न्यूनतम अंतरालन, और मूव16 के बाद [[सिल्वर कॉइनेज]] के विजेता सहित पुरस्कार समस्याओं का एक हिस्सा भी सम्मिलित है।<ref>{{citation
रूप में हर थ्रैकल में कम से कम उतने ही धब्बे होते हैं जितने पथ होते हैं। कॉनवे ने इस अनुमान को साबित करने या अस्वीकार करने के लिए $ 1000 पुरस्कार की पेशकश की, जिसमें कॉनवे की 99-ग्राफ की समस्या, [[ डांसर सेट ]] की न्यूनतम रिक्ति, और चाल 16 के बाद [[चाँदी का सिक्का]] के विजेता सहित पुरस्कार समस्याओं का एक हिस्सा भी शामिल है।<ref>{{citation
  | last = Conway | first = John H. | author-link = John Horton Conway
  | last = Conway | first = John H. | author-link = John Horton Conway
  | accessdate = 2019-02-12
  | accessdate = 2019-02-12
Line 29: Line 30:
  | title = Five $1,000 Problems (Update 2017)
  | title = Five $1,000 Problems (Update 2017)
  | url = https://oeis.org/A248380/a248380.pdf}}</ref>
  | url = https://oeis.org/A248380/a248380.pdf}}</ref>
समतुल्य रूप से, थ्रैकल अनुमान को कहा जा सकता है क्योंकि प्रत्येक थ्रैकल एक स्यूडोफॉरेस्ट है। अधिक विशेष रूप से, यदि थ्रैकल अनुमान सत्य है, तो थ्रैकल्स को वुडाल के परिणाम से सटीक रूप से चित्रित किया जा सकता है: वे छद्म वन हैं जिनमें लंबाई चार का कोई चक्र नहीं है और अधिक से अधिक एक विषम चक्र है।<ref name="lps"/><ref name="woodall">{{citation |first=D. R. |last=Woodall |contribution=Thrackles and deadlock |title=Combinatorial Mathematics and Its Applications |editor-first=D. J. A. |editor-last=Welsh |publisher=Academic Press |year=1969 |pages=335–348 |mr=0277421 }}.</ref>
तुल्यतः, थ्रैकल अनुमान को कहा जा सकता है क्योंकि प्रत्येक थ्रैकल एक ''[[स्यूडोफॉरेस्ट]]'' है। अधिक विशेष रूप से, यदि थ्रैकल अनुमान सत्य है, तो थ्रैकल्स को वुडाल के परिणाम से सटीक रूप से चित्रित किया जा सकता है: वे स्यूडोफॉरेस्ट हैं जिनमें लंबाई चार का कोई चक्र नहीं है और अधिक से अधिक एक विषम चक्र है।<ref name="lps" /><ref name="woodall">{{citation |first=D. R. |last=Woodall |contribution=Thrackles and deadlock |title=Combinatorial Mathematics and Its Applications |editor-first=D. J. A. |editor-last=Welsh |publisher=Academic Press |year=1969 |pages=335–348 |mr=0277421 }}.</ref>
यह सिद्ध हो चुका है कि C के अलावा हर चक्र का ग्राफ<sub>4</sub> एक थ्रैकल एम्बेडिंग है, जो दर्शाता है कि अनुमान गणितीय शब्दजाल की सूची#sharp है। यानी, पथ के समान स्पॉट वाले थ्रैकल हैं। दूसरे चरम पर, सबसे खराब स्थिति यह है कि स्पॉट की संख्या पथों की संख्या से दोगुनी है; यह भी प्राप्य है।
 
यह सिद्ध हो चुका है कि C<sub>4</sub> के अतिरिक्त हर चक्र ग्राफ में एक थ्रैकल अंत: स्थापन है, जो दर्शाता है कि अनुमान [[तीव्र]] (शार्प) है। यानी, पथ के समान स्पॉट वाले थ्रैकल हैं। दूसरे चरम पर, सबसे खराब स्थिति यह है कि स्पॉट की संख्या पथों की संख्या से दोगुनी है; यह भी प्राप्य है।


थ्रैकल अनुमान इस तरह से खींचे गए थ्रैकल्स के लिए सही माना जाता है कि प्रत्येक किनारा एक एक्स-मोनोटोन वक्र है, जो प्रत्येक ऊर्ध्वाधर रेखा द्वारा अधिकतम एक बार पार किया जाता है।<ref name="pach">{{citation
थ्रैकल अनुमान इस तरह से खींचे गए थ्रैकल्स के लिए सही माना जाता है कि प्रत्येक किनारा एक x-एकदिष्ट वक्र है, जो प्रत्येक ऊर्ध्वाधर रेखा द्वारा अधिकतम एक बार पार किया जाता है।<ref name="pach">{{citation
  | last1 = Pach | first1 = János | author1-link = János Pach
  | last1 = Pach | first1 = János | author1-link = János Pach
  | last2 = Sterling | first2 = Ethan
  | last2 = Sterling | first2 = Ethan
Line 43: Line 45:
  | volume = 118
  | volume = 118
  | year = 2011}}.</ref>
  | year = 2011}}.</ref>




== ज्ञात सीमा ==
== ज्ञात सीमा ==
{{harvtxt|Lovász|Pach|Szegedy|1997}} ने साबित किया कि प्रत्येक [[द्विपक्षीय ग्राफ]] थ्रैकल एक [[ प्लेनर ग्राफ ]] है, हालांकि प्लानर तरीके से नहीं खींचा गया है।<ref name="lps"/>परिणामस्वरूप, वे दिखाते हैं कि n शीर्षों वाले प्रत्येक थ्रैकलीबल ग्राफ़ में अधिक से अधिक 2n − 3 किनारे होते हैं। तब से, इस सीमा में कई बार सुधार किया गया है। सबसे पहले, इसे 3(n − 1)/2 में सुधारा गया था,<ref>{{citation |last1=Cairns |first1=G. |last2=Nikolayevsky |first2=Y. |title=Bounds for generalized thrackles |journal=Discrete and Computational Geometry |volume=23 |year=2000 |issue=2 |pages=191–206 |mr=1739605 |doi=10.1007/PL00009495|doi-access=free }}.</ref> और एक अन्य सुधार के कारण मोटे तौर पर 1.428n का बाउंड हुआ।<ref name="fp">{{citation |last1=Fulek |first1=R. |last2=Pach |first2=J.|author2-link=János Pach |title=A computational approach to Conway's thrackle conjecture|journal= Computational Geometry |volume=44 |year=2011|issue=6–7 |pages=345–355 |mr=2785903 |doi=10.1007/978-3-642-18469-7_21|arxiv=1002.3904 }}.</ref> इसके अलावा, बाद के परिणाम को साबित करने के लिए इस्तेमाल की जाने वाली विधि किसी भी ε > 0 के लिए एक परिमित एल्गोरिथ्म है जो या तो
{{harvtxt|लोवास्ज |पच |स्जेगेडी|1997}} ने सिद्ध किया कि प्रत्येक [[द्विपक्षीय ग्राफ|द्विपक्षीय]] (बाइपार्टाइट) थ्रैकल एक[[ प्लेनर ग्राफ | समतली ग्राफ]] है, हालांकि समतली तरीके से नहीं खींचा गया है।<ref name="lps"/> परिणामस्वरूप, वे दिखाते हैं कि ''n'' शीर्षों वाले प्रत्येक थ्रैकलेबल ग्राफ़ में अधिकतम 2n − 3 किनारे होते हैं। तब से, इस सीमा (परिबद्ध) में कई बार सुधार किया गया है। सबसे पहले, इसे 3(''n'' − 1)/2 में सुधारा गया था,<ref>{{citation |last1=Cairns |first1=G. |last2=Nikolayevsky |first2=Y. |title=Bounds for generalized thrackles |journal=Discrete and Computational Geometry |volume=23 |year=2000 |issue=2 |pages=191–206 |mr=1739605 |doi=10.1007/PL00009495|doi-access=free }}.</ref> और दूसरे सुधार के कारण साधारणतया ''1.428n'' की सीमा हो गई थी।<ref name="fp">{{citation |last1=Fulek |first1=R. |last2=Pach |first2=J.|author2-link=János Pach |title=A computational approach to Conway's thrackle conjecture|journal= Computational Geometry |volume=44 |year=2011|issue=6–7 |pages=345–355 |mr=2785903 |doi=10.1007/978-3-642-18469-7_21|arxiv=1002.3904 }}.</ref> इसके अलावा, बाद के परिणाम को सिद्ध करने के लिए उपयोग की जाने वाली विधि किसी भी ε > 0 के लिए एक परिमित एल्गोरिथ्म है जो या तो (1 + ε)n के लिए परिबद्ध में सुधार करती है या अनुमान को असत्य सिद्ध करती है। वर्तमान रिकॉर्ड {{harvtxt|फुलेक |पाच |2017}} के कारण है, जिन्होंने ''1.3984n'' की सीमा सिद्ध की है।<ref name="fp2">{{citation |last1=Fulek |first1=R. |last2=Pach |first2=J.|author2-link=János Pach |title=Graph Drawing and Network Visualization: 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers |contribution=Thrackles: An improved upper bound |series= Lecture Notes in Computer Science |year=2017|volume=10692 | pages=160–166 |doi=10.1007/978-3-319-73915-1_14|arxiv=1708.08037 |isbn=978-3-319-73914-4 }}.</ref>
(1 + ε)n की सीमा में सुधार करता है या अनुमान को गलत साबित करता है। वर्तमान रिकॉर्ड के कारण है {{harvtxt|Fulek|Pach|2017}}, जिन्होंने 1.3984n की सीमा सिद्ध की।<ref name="fp2">{{citation |last1=Fulek |first1=R. |last2=Pach |first2=J.|author2-link=János Pach |title=Graph Drawing and Network Visualization: 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers |contribution=Thrackles: An improved upper bound |series= Lecture Notes in Computer Science |year=2017|volume=10692 | pages=160–166 |doi=10.1007/978-3-319-73915-1_14|arxiv=1708.08037 |isbn=978-3-319-73914-4 }}.</ref>
 
यदि अनुमान गलत है, तो एक न्यूनतम प्रति उदाहरण में एक शीर्ष साझा करने वाले दो समान चक्रों का रूप होगा।<ref name="woodall"/>इसलिए, अनुमान को सिद्ध करने के लिए, यह साबित करना पर्याप्त होगा कि इस प्रकार के ग्राफ़ को थ्रैकल्स के रूप में नहीं खींचा जा सकता है।
यदि अनुमान गलत है, तो एक न्यूनतम गणित्र उदाहरण में एक शीर्ष साझा करने वाले दो समान चक्रों का रूप होता है।<ref name="woodall" /> इसलिए, अनुमान को सिद्ध करने के लिए, यह सिद्ध करना पर्याप्त होगा कि इस प्रकार के ग्राफ़ को थ्रैकल्स के रूप में नहीं खींचा जा सकता है।


== संदर्भ ==
== संदर्भ ==
Line 56: Line 59:
==बाहरी संबंध==
==बाहरी संबंध==
* [http://www.thrackle.org  thrackle.org]—website about the problem
* [http://www.thrackle.org  thrackle.org]—website about the problem
[[Category: अनुमान]] [[Category: सामयिक ग्राफ सिद्धांत]] [[Category: ज्यामितीय चौराहा]]


[[Category: Machine Translated Page]]
[[Category:Created On 19/05/2023]]
[[Category:Created On 19/05/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:अनुमान]]
[[Category:ज्यामितीय चौराहा]]
[[Category:सामयिक ग्राफ सिद्धांत]]

Latest revision as of 16:14, 8 June 2023

एक थ्रैकल तल में एक ग्राफ का एक अंतःस्थापन (एम्बेडिंग) है, जैसे कि प्रत्येक किनारा एक जॉर्डन चाप है और और किनारों का हर युग्म ठीक एक बार मिलता है। किनारे या तो एक सामान्य अंत बिंदु पर मिल सकते हैं, या, यदि उनके पास कोई अंत बिंदु नहीं है, तो उनके आंतरिक भाग में एक बिंदु पर मिल सकते हैं। बाद की स्थिति में, क्रॉसिंग अनुप्रस्थ होना चाहिए।[1]


रैखिक थ्रैकल्स

चार रेनहार्ड्ट बहुभुज। उनके व्यास (नीला) रैखिक थ्रैकल्स बनाते हैं।

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

मीका पर्ल्स ने एक और सरल प्रमाण प्रदान किया कि रैखिक थ्रैकल्स में अधिकांश n किनारे होते हैं, इस तथ्य के आधार पर कि एक रेखीय थ्रैकल में प्रत्येक किनारे का एक अंत बिंदु होता है, जिस पर किनारे अधिकतम 180 ° के कोण पर विस्तृति होते हैं, और जिसके लिए यह इस सीमा (स्पैन) के अंदर सबसे अधिक दक्षिणावर्त किनारा होता है। इसके लिए, यदि नहीं, तो दो किनारे होंगे, किनारे के विपरीत अंत बिदुओं के लिए घटना और किनारे के माध्यम से रेखा की विपरीत किनारों पर लाइंग होना, जो एक दूसरे को क्रॉस नहीं कर सके है। लेकिन प्रत्येक शीर्ष में केवल एक किनारे के संबंध में यह गुण हो सकता है, इसलिए किनारों की संख्या अधिक से अधिक शीर्षों की संख्या के बराबर होती है।[3]

जैसा कि एर्डोस ने भी देखा, बिंदु समुच्चय के व्यास को प्राप्त करने वाले बिंदुओं के युग्मों के समुच्चय को एक रैखिक थ्रैकल बनाना चाहिए: कोई भी दो व्यासों को एक दूसरे से अलग नहीं किया जा सकता है, क्योंकि यदि वे होते तो उनके चार अंतबिंदुओं में दो असंयुक्त किनारों के अलावा दूर की दूरी पर एक युग्म होता है। इस कारण से, तल में n बिंदुओं के प्रत्येक समुच्चय में अधिक से अधिक n व्यास युग्म हो सकते हैं, जो हेंज हॉफ और एरिका पन्नविट्ज़ द्वारा 1934 में पूछे गए एक प्रश्न का उत्तर देते हैं।[4] एंड्रयू वाज़सोनी ने इस समस्या को सामान्य करते हुए, उच्च आयामों में व्यास युग्मों की संख्या पर अनुमान लगाया था।[2]

अभिकलनी ज्यामिति में, घूर्णन कैलीपर्स की विधि का उपयोग अवमुख स्थिति में बिंदुओं के किसी भी समुच्चय से एक रैखिक थ्रैकल बनाने के लिए किया जा सकता है, बिंदुओं के युग्मों को जोड़कर जो बिंदुओं के अवमुख हल को समानांतर रेखाओं का समर्थन करते हैं।[5] इस ग्राफ में व्यास युग्मों के थ्रैकल को उपग्राफ के रूप में सम्मिलित किया गया है।[6]

रेनहार्ड्ट बहुभुजों के व्यास रैखिक थ्रैकल बनाते हैं। सबसे बड़ी छोटी बहुभुज समस्या को हल करने के लिए रैखिक थ्रैकल्स की गणना का उपयोग किया जा सकता है, इसके व्यास के सापेक्ष अधिकतम क्षेत्र के साथ n-गॉन खोजने के लिए किया जा सकता है।[7]


थ्रैकल अनुमान

Unsolved problem in mathematics:

Can a thrackle have more edges than vertices?

(more unsolved problems in mathematics)
6-चक्र ग्राफ का एक थ्रैकल अंत:स्थापन।

जॉन एच. कॉनवे ने अनुमान लगाया कि, किसी भी थ्रैकल में किनारों की संख्या अधिक से अधिक शीर्षों की संख्या के बराबर होती है। कॉनवे ने स्वयं शब्दावली (टर्मिनोलॉजी) पथ और स्पॉट (क्रमशः किनारों और शीर्षों के लिए) का उपयोग किया, इसलिए कॉनवे के थ्रैकल अनुमान को मूल रूप से कहा गया था कि हर थ्रैकल में पथ के रूप में कम से कम कई स्पॉट हैं। कॉनवे ने इस अनुमान को सिद्ध करने या असत्य सिद्ध करने के लिए $ 1000 पुरस्कार का प्रस्ताव रखा, जिसमें कॉनवे की 99-ग्राफ की समस्या, डेनजर समुच्चय का न्यूनतम अंतरालन, और मूव16 के बाद सिल्वर कॉइनेज के विजेता सहित पुरस्कार समस्याओं का एक हिस्सा भी सम्मिलित है।[8]

तुल्यतः, थ्रैकल अनुमान को कहा जा सकता है क्योंकि प्रत्येक थ्रैकल एक स्यूडोफॉरेस्ट है। अधिक विशेष रूप से, यदि थ्रैकल अनुमान सत्य है, तो थ्रैकल्स को वुडाल के परिणाम से सटीक रूप से चित्रित किया जा सकता है: वे स्यूडोफॉरेस्ट हैं जिनमें लंबाई चार का कोई चक्र नहीं है और अधिक से अधिक एक विषम चक्र है।[1][9]

यह सिद्ध हो चुका है कि C4 के अतिरिक्त हर चक्र ग्राफ में एक थ्रैकल अंत: स्थापन है, जो दर्शाता है कि अनुमान तीव्र (शार्प) है। यानी, पथ के समान स्पॉट वाले थ्रैकल हैं। दूसरे चरम पर, सबसे खराब स्थिति यह है कि स्पॉट की संख्या पथों की संख्या से दोगुनी है; यह भी प्राप्य है।

थ्रैकल अनुमान इस तरह से खींचे गए थ्रैकल्स के लिए सही माना जाता है कि प्रत्येक किनारा एक x-एकदिष्ट वक्र है, जो प्रत्येक ऊर्ध्वाधर रेखा द्वारा अधिकतम एक बार पार किया जाता है।[3]


ज्ञात सीमा

लोवास्ज, पच & स्जेगेडी (1997) ने सिद्ध किया कि प्रत्येक द्विपक्षीय (बाइपार्टाइट) थ्रैकल एक समतली ग्राफ है, हालांकि समतली तरीके से नहीं खींचा गया है।[1] परिणामस्वरूप, वे दिखाते हैं कि n शीर्षों वाले प्रत्येक थ्रैकलेबल ग्राफ़ में अधिकतम 2n − 3 किनारे होते हैं। तब से, इस सीमा (परिबद्ध) में कई बार सुधार किया गया है। सबसे पहले, इसे 3(n − 1)/2 में सुधारा गया था,[10] और दूसरे सुधार के कारण साधारणतया 1.428n की सीमा हो गई थी।[11] इसके अलावा, बाद के परिणाम को सिद्ध करने के लिए उपयोग की जाने वाली विधि किसी भी ε > 0 के लिए एक परिमित एल्गोरिथ्म है जो या तो (1 + ε)n के लिए परिबद्ध में सुधार करती है या अनुमान को असत्य सिद्ध करती है। वर्तमान रिकॉर्ड फुलेक & पाच (2017) के कारण है, जिन्होंने 1.3984n की सीमा सिद्ध की है।[12]

यदि अनुमान गलत है, तो एक न्यूनतम गणित्र उदाहरण में एक शीर्ष साझा करने वाले दो समान चक्रों का रूप होता है।[9] इसलिए, अनुमान को सिद्ध करने के लिए, यह सिद्ध करना पर्याप्त होगा कि इस प्रकार के ग्राफ़ को थ्रैकल्स के रूप में नहीं खींचा जा सकता है।

संदर्भ

  1. ↑ 1.0 1.1 1.2 Lovász, L.; Pach, J.; Szegedy, M. (1997), "On Conway's thrackle conjecture", Discrete and Computational Geometry, 18 (4): 369–376, doi:10.1007/PL00009322, MR 1476318. A preliminary version of these results was reviewed in O'Rourke, J. (1995), "Computational geometry column 26", ACM SIGACT News, 26 (2): 15–17, arXiv:cs/9908007, doi:10.1145/202840.202842.
  2. ↑ 2.0 2.1 Erdős, P. (1946), "On sets of distances of n points" (PDF), American Mathematical Monthly, 53 (5): 248–250, doi:10.2307/2305092, JSTOR 2305092.
  3. ↑ 3.0 3.1 Pach, János; Sterling, Ethan (2011), "Conway's conjecture for monotone thrackles", American Mathematical Monthly, 118 (6): 544–548, doi:10.4169/amer.math.monthly.118.06.544, MR 2812285.
  4. ↑ Hopf, H.; Pannwitz, E. (1934), "Aufgabe Nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung, 43: 114.
  5. ↑ Eppstein, David (May 1995), "The Rotating Caliper Graph", The Geometry Junkyard
  6. ↑ For the fact that the rotating caliper graph contains all diameter pairs, see Shamos, Michael (1978), Computational Geometry (PDF), Doctoral dissertation, Yale University. For the fact that the diameter pairs form a thrackle, see, e.g., Pach & Sterling (2011).
  7. ↑ Graham, R. L. (1975), "The largest small hexagon" (PDF), Journal of Combinatorial Theory, Series A, 18 (2): 165–170, doi:10.1016/0097-3165(75)90004-7.
  8. ↑ Conway, John H., Five $1,000 Problems (Update 2017) (PDF), Online Encyclopedia of Integer Sequences, retrieved 2019-02-12
  9. ↑ 9.0 9.1 Woodall, D. R. (1969), "Thrackles and deadlock", in Welsh, D. J. A. (ed.), Combinatorial Mathematics and Its Applications, Academic Press, pp. 335–348, MR 0277421.
  10. ↑ Cairns, G.; Nikolayevsky, Y. (2000), "Bounds for generalized thrackles", Discrete and Computational Geometry, 23 (2): 191–206, doi:10.1007/PL00009495, MR 1739605.
  11. ↑ Fulek, R.; Pach, J. (2011), "A computational approach to Conway's thrackle conjecture", Computational Geometry, 44 (6–7): 345–355, arXiv:1002.3904, doi:10.1007/978-3-642-18469-7_21, MR 2785903.
  12. ↑ Fulek, R.; Pach, J. (2017), "Thrackles: An improved upper bound", Graph Drawing and Network Visualization: 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers, Lecture Notes in Computer Science, vol. 10692, pp. 160–166, arXiv:1708.08037, doi:10.1007/978-3-319-73915-1_14, ISBN 978-3-319-73914-4.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=थ्रैकल&oldid=177461’