थ्रैकल: Difference between revisions
No edit summary |
No edit summary |
||
| 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> | ||
और किनारों का हर | |||
| Line 8: | Line 7: | ||
[[मीका मोती]] ने एक और सरल प्रमाण प्रदान किया कि रैखिक थ्रैकल्स में अधिकांश n किनारे होते हैं, इस तथ्य के आधार पर कि एक रेखीय थ्रैकल में प्रत्येक किनारे का एक समापन बिंदु होता है, जिस पर किनारे अधिकतम 180 ° के कोण पर फैले होते हैं, और जिसके लिए यह सबसे अधिक दक्षिणावर्त होता है। इस अवधि के भीतर बढ़त। इसके लिए, यदि नहीं, तो दो किनारे होंगे, किनारे के विपरीत छोरों के लिए घटना और किनारे के माध्यम से रेखा के विपरीत किनारों पर झूठ बोलना, जो एक दूसरे को पार नहीं कर सके। लेकिन प्रत्येक शीर्ष में केवल एक किनारे के संबंध में यह गुण हो सकता है, इसलिए किनारों की संख्या अधिक से अधिक वर्टिकल की संख्या के बराबर होती है।<ref name="pach"/> | [[मीका मोती]] ने एक और सरल प्रमाण प्रदान किया कि रैखिक थ्रैकल्स में अधिकांश n किनारे होते हैं, इस तथ्य के आधार पर कि एक रेखीय थ्रैकल में प्रत्येक किनारे का एक समापन बिंदु होता है, जिस पर किनारे अधिकतम 180 ° के कोण पर फैले होते हैं, और जिसके लिए यह सबसे अधिक दक्षिणावर्त होता है। इस अवधि के भीतर बढ़त। इसके लिए, यदि नहीं, तो दो किनारे होंगे, किनारे के विपरीत छोरों के लिए घटना और किनारे के माध्यम से रेखा के विपरीत किनारों पर झूठ बोलना, जो एक दूसरे को पार नहीं कर सके। लेकिन प्रत्येक शीर्ष में केवल एक किनारे के संबंध में यह गुण हो सकता है, इसलिए किनारों की संख्या अधिक से अधिक वर्टिकल की संख्या के बराबर होती है।<ref name="pach"/> | ||
जैसा कि एर्दोस ने भी देखा, बिंदु सेट के [[व्यास]] को महसूस करने वाले बिंदुओं के जोड़े के सेट को एक रैखिक थ्रैकल बनाना चाहिए: कोई भी दो व्यास एक दूसरे से अलग नहीं हो सकते हैं, क्योंकि यदि वे थे तो उनके चार समापन बिंदु अलग-अलग दूरी पर एक जोड़ी होगी दो अलग-अलग किनारों की तुलना में। इस कारण से, | जैसा कि एर्दोस ने भी देखा, बिंदु सेट के [[व्यास]] को महसूस करने वाले बिंदुओं के जोड़े के सेट को एक रैखिक थ्रैकल बनाना चाहिए: कोई भी दो व्यास एक दूसरे से अलग नहीं हो सकते हैं, क्योंकि यदि वे थे तो उनके चार समापन बिंदु अलग-अलग दूरी पर एक जोड़ी होगी दो अलग-अलग किनारों की तुलना में। इस कारण से, तल में 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 | ||
Revision as of 07:13, 26 May 2023
एक थ्रैकल तल में एक ग्राफ का एक अंतःस्थापन (एम्बेडिंग) है, जैसे कि प्रत्येक किनारा एक जॉर्डन चाप है और और किनारों का हर युग्म बिल्कुल एक बार मिलता है। किनारे या तो एक सामान्य अंत बिंदु पर मिल सकते हैं, या, यदि उनके पास कोई अंत बिंदु नहीं है, तो उनके आंतरिक भाग में एक बिंदु पर मिल सकते हैं। बाद की स्थिति में, क्रॉसिंग अनुप्रस्थ होना चाहिए।[1]
रैखिक थ्रैकल्स
एक रैखिक थ्रैकल इस तरह से खींचा गया थ्रैकल है कि इसके किनारे सीधी रेखा खंड हैं। जैसा कि पॉल एर्डोस ने देखा, प्रत्येक रैखिक थ्रैकल में अधिक से अधिक किनारों के रूप में कोने होते हैं। यदि एक शीर्ष v तीन या अधिक किनारों vw, vx, और vy से जुड़ा है, तो उन किनारों में से कम से कम एक किनारा ("vw" कहें) पर स्थित है एक रेखा जो दो अन्य किनारों को अलग करती है। फिर, w के पास डिग्री (ग्राफ़ थ्योरी) एक होनी चाहिए, क्योंकि vw के अलावा w पर समाप्त होने वाला कोई भी रेखा खंड, vx और vy दोनों को नहीं छू सकता है। . w और vw को हटाने से किनारों और शीर्षों की संख्या के बीच के अंतर को बदले बिना एक छोटा थ्रैकल पैदा होता है। इस तरह से हटाने के बाद एक थ्रैकल होता है जिसमें प्रत्येक शीर्ष पर अधिकतम दो पड़ोसी होते हैं, हाथ मिलाना लेम्मा द्वारा किनारों की संख्या अधिक से अधिक वर्टिकल की संख्या होती है।[2] एर्दोस के प्रमाण के आधार पर, कोई भी अनुमान लगा सकता है कि प्रत्येक रैखिक थ्रैकल एक seudoforest है। विषम लंबाई के प्रत्येक चक्र को एक रेखीय थ्रैकल बनाने के लिए व्यवस्थित किया जा सकता है, लेकिन यह समान-लंबाई वाले चक्र के लिए संभव नहीं है, क्योंकि यदि चक्र के एक किनारे को मनमाने ढंग से चुना जाता है, तो दूसरे चक्र के कोने बारी-बारी से रेखा के विपरीत दिशा में स्थित होने चाहिए। इस किनारे के माध्यम से।
मीका मोती ने एक और सरल प्रमाण प्रदान किया कि रैखिक थ्रैकल्स में अधिकांश n किनारे होते हैं, इस तथ्य के आधार पर कि एक रेखीय थ्रैकल में प्रत्येक किनारे का एक समापन बिंदु होता है, जिस पर किनारे अधिकतम 180 ° के कोण पर फैले होते हैं, और जिसके लिए यह सबसे अधिक दक्षिणावर्त होता है। इस अवधि के भीतर बढ़त। इसके लिए, यदि नहीं, तो दो किनारे होंगे, किनारे के विपरीत छोरों के लिए घटना और किनारे के माध्यम से रेखा के विपरीत किनारों पर झूठ बोलना, जो एक दूसरे को पार नहीं कर सके। लेकिन प्रत्येक शीर्ष में केवल एक किनारे के संबंध में यह गुण हो सकता है, इसलिए किनारों की संख्या अधिक से अधिक वर्टिकल की संख्या के बराबर होती है।[3]
जैसा कि एर्दोस ने भी देखा, बिंदु सेट के व्यास को महसूस करने वाले बिंदुओं के जोड़े के सेट को एक रैखिक थ्रैकल बनाना चाहिए: कोई भी दो व्यास एक दूसरे से अलग नहीं हो सकते हैं, क्योंकि यदि वे थे तो उनके चार समापन बिंदु अलग-अलग दूरी पर एक जोड़ी होगी दो अलग-अलग किनारों की तुलना में। इस कारण से, तल में n बिंदुओं के प्रत्येक सेट में अधिक से अधिक n व्यास जोड़े हो सकते हैं, जो हेंज हॉफ और एरिका पन्नविट्ज़ द्वारा 1934 में पूछे गए एक प्रश्न का उत्तर देते हैं।[4] एंड्रयू वाज़सोनी ने इस समस्या को सामान्य करते हुए, उच्च आयामों में व्यास जोड़े की संख्या पर अनुमान लगाया।[2]
कम्प्यूटेशनल ज्यामिति में, कैलीपर्स को घुमाने की विधि का उपयोग उत्तल स्थिति में बिंदुओं के किसी भी सेट से एक रैखिक थ्रैकल बनाने के लिए किया जा सकता है, बिंदुओं के जोड़े को जोड़कर जो बिंदुओं के उत्तल हल को समानांतर रेखाओं का समर्थन करते हैं।[5] इस ग्राफ में व्यास जोड़े के थ्रैकल को सबग्राफ के रूप में शामिल किया गया है।[6] रेनहार्ड्ट बहुभुजों के व्यास रैखिक थ्रैकल बनाते हैं। सबसे बड़ी छोटी बहुभुज समस्या को हल करने के लिए रैखिक थ्रैकल्स की गणना का उपयोग किया जा सकता है, इसके व्यास के सापेक्ष अधिकतम क्षेत्र के साथ एन-गॉन खोजने के लिए।[7]
थ्रैकल अनुमान
Can a thrackle have more edges than vertices?
जॉन हॉर्टन कॉनवे|जॉन एच. कॉनवे ने अनुमान लगाया कि, किसी भी थ्रैकल में, किनारों की संख्या अधिक से अधिक शीर्षों की संख्या के बराबर होती है। कॉनवे ने खुद शब्दावली पथ और स्पॉट (क्रमशः किनारों और कोने के लिए) का इस्तेमाल किया, इसलिए 'कॉनवे का थ्रैकल अनुमान' मूल रूप से कहा गया था
रूप में हर थ्रैकल में कम से कम उतने ही धब्बे होते हैं जितने पथ होते हैं। कॉनवे ने इस अनुमान को साबित करने या अस्वीकार करने के लिए $ 1000 पुरस्कार की पेशकश की, जिसमें कॉनवे की 99-ग्राफ की समस्या, डांसर सेट की न्यूनतम रिक्ति, और चाल 16 के बाद चाँदी का सिक्का के विजेता सहित पुरस्कार समस्याओं का एक हिस्सा भी शामिल है।[8] समतुल्य रूप से, थ्रैकल अनुमान को कहा जा सकता है क्योंकि प्रत्येक थ्रैकल एक स्यूडोफॉरेस्ट है। अधिक विशेष रूप से, यदि थ्रैकल अनुमान सत्य है, तो थ्रैकल्स को वुडाल के परिणाम से सटीक रूप से चित्रित किया जा सकता है: वे छद्म वन हैं जिनमें लंबाई चार का कोई चक्र नहीं है और अधिक से अधिक एक विषम चक्र है।[1][9] यह सिद्ध हो चुका है कि C के अलावा हर चक्र का ग्राफ4 एक थ्रैकल एम्बेडिंग है, जो दर्शाता है कि अनुमान गणितीय शब्दजाल की सूची#sharp है। यानी, पथ के समान स्पॉट वाले थ्रैकल हैं। दूसरे चरम पर, सबसे खराब स्थिति यह है कि स्पॉट की संख्या पथों की संख्या से दोगुनी है; यह भी प्राप्य है।
थ्रैकल अनुमान इस तरह से खींचे गए थ्रैकल्स के लिए सही माना जाता है कि प्रत्येक किनारा एक एक्स-मोनोटोन वक्र है, जो प्रत्येक ऊर्ध्वाधर रेखा द्वारा अधिकतम एक बार पार किया जाता है।[3]
ज्ञात सीमा
Lovász, Pach & Szegedy (1997) ने साबित किया कि प्रत्येक द्विपक्षीय ग्राफ थ्रैकल एक प्लेनर ग्राफ है, हालांकि प्लानर तरीके से नहीं खींचा गया है।[1]परिणामस्वरूप, वे दिखाते हैं कि n शीर्षों वाले प्रत्येक थ्रैकलीबल ग्राफ़ में अधिक से अधिक 2n − 3 किनारे होते हैं। तब से, इस सीमा में कई बार सुधार किया गया है। सबसे पहले, इसे 3(n − 1)/2 में सुधारा गया था,[10] और एक अन्य सुधार के कारण मोटे तौर पर 1.428n का बाउंड हुआ।[11] इसके अलावा, बाद के परिणाम को साबित करने के लिए इस्तेमाल की जाने वाली विधि किसी भी ε > 0 के लिए एक परिमित एल्गोरिथ्म है जो या तो (1 + ε)n की सीमा में सुधार करता है या अनुमान को गलत साबित करता है। वर्तमान रिकॉर्ड के कारण है Fulek & Pach (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
