थ्रैकल: Difference between revisions
No edit summary |
|||
| Line 49: | Line 49: | ||
== ज्ञात सीमा == | == ज्ञात सीमा == | ||
{{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> और | {{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> | ||
यदि अनुमान गलत है, तो एक न्यूनतम गणित्र उदाहरण में एक शीर्ष साझा करने वाले दो समान चक्रों का रूप होता है।<ref name="woodall" />इसलिए, अनुमान को सिद्ध करने के लिए, यह सिद्ध करना पर्याप्त होगा कि इस प्रकार के ग्राफ़ को थ्रैकल्स के रूप में नहीं खींचा जा सकता है। | यदि अनुमान गलत है, तो एक न्यूनतम गणित्र उदाहरण में एक शीर्ष साझा करने वाले दो समान चक्रों का रूप होता है।<ref name="woodall" /> इसलिए, अनुमान को सिद्ध करने के लिए, यह सिद्ध करना पर्याप्त होगा कि इस प्रकार के ग्राफ़ को थ्रैकल्स के रूप में नहीं खींचा जा सकता है। | ||
== संदर्भ == | == संदर्भ == | ||
Revision as of 12:37, 26 May 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]
थ्रैकल अनुमान
Can a thrackle have more edges than vertices?
जॉन एच. कॉनवे ने अनुमान लगाया कि, किसी भी थ्रैकल में किनारों की संख्या अधिक से अधिक शीर्षों की संख्या के बराबर होती है। कॉनवे ने स्वयं शब्दावली (टर्मिनोलॉजी) पथ और स्पॉट (क्रमशः किनारों और शीर्षों के लिए) का उपयोग किया, इसलिए कॉनवे के थ्रैकल अनुमान को मूल रूप से कहा गया था कि हर थ्रैकल में पथ के रूप में कम से कम कई स्पॉट हैं। कॉनवे ने इस अनुमान को सिद्ध करने या असत्य सिद्ध करने के लिए $ 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.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.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.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.
- ↑ Hopf, H.; Pannwitz, E. (1934), "Aufgabe Nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung, 43: 114.
- ↑ Eppstein, David (May 1995), "The Rotating Caliper Graph", The Geometry Junkyard
- ↑ 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).
- ↑ 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.
- ↑ Conway, John H., Five $1,000 Problems (Update 2017) (PDF), Online Encyclopedia of Integer Sequences, retrieved 2019-02-12
- ↑ 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.
- ↑ Cairns, G.; Nikolayevsky, Y. (2000), "Bounds for generalized thrackles", Discrete and Computational Geometry, 23 (2): 191–206, doi:10.1007/PL00009495, MR 1739605.
- ↑ 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.
- ↑ 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.
बाहरी संबंध
- thrackle.org—website about the problem
