जियोडेटिक ग्राफ: Difference between revisions
(Created page with "{{Short description|Graph whose shortest paths are unique}} ग्राफ़ थ्योरी में, एक जियोडेटिक ग्राफ़ एक अ...") |
(text) |
||
| Line 1: | Line 1: | ||
{{Short description|Graph whose shortest paths are unique}} | {{Short description|Graph whose shortest paths are unique}} | ||
आलेख सिद्धांत में, एक भूगणितीय लेखाचित्र एक [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष]] लेखाचित्र होता है जैसे कि प्रत्येक दो शिखरों के बीच एक अद्वितीय (अभारित) सबसे छोटा पथ उपस्थित होता है। | |||
1962 में | 1962 में ऑयस्टीन अयस्क द्वारा भूगणितीय लेखाचित्र प्रस्तुत किए गए थे, जिन्होंने देखा कि वे तरू की एक विशेषता का सामान्यीकरण करते हैं (जिसमें दूरी की चिंता किए बिना प्रत्येक दो शीर्षों के बीच एक अद्वितीय पथ उपस्थित है), और उनके चित्रण वर्णन के लिए कहा गया। {{r|ore}} हालांकि इन लेखाचित्रों को बहुपद समय में पहचाना जा सकता है, साठ से अधिक वर्षों के बाद एक पूर्ण लक्षण वर्णन अभी भी दुर्ग्राह्य है।{{r|cghks}} | ||
== उदाहरण == | == उदाहरण == | ||
हर | हर तरू (लेखाचित्र सिद्धांत),{{r|ore}} हर [[पूरा ग्राफ|पूरा लेखाचित्र]],{{r|gc}} और प्रत्येक विषम-लंबाई [[चक्र ग्राफ|चक्र लेखाचित्र]] भूगणितीय है।{{r|sw}} | ||
यदि <math>G</math> एक भूगणितीय लेखाचित्र है, तो G के प्रत्येक किनारे को उसी विषम लंबाई के पथ से बदलने से एक और भूगणितीय लेखाचित्र उत्पन्न होगा।{{r|ps}} | |||
पूर्ण लेखाचित्र की स्तिथियों में, पथों द्वारा प्रतिस्थापन का एक अधिक सामान्य प्रतिरूप संभव है: प्रत्येक शीर्ष <math>v</math> के लिए एक गैर-ऋणात्मक पूर्णांक <math>f(v)</math> चुनें, और इसमें <math>f(u)+f(v)</math> कोने जोड़कर प्रत्येक किनारे <math>uv</math> को उपविभाजित करें। फिर परिणामी उप-विभाजित पूर्ण लेखाचित्र भूगणितीय है, और प्रत्येक भूगणितीय उप-विभाजित पूर्ण लेखाचित्र इस तरह से प्राप्त किया जा सकता है।{{r|plesnik|stemple}} | |||
== | == संबंधित लेखाचित्र वर्ग == | ||
बहुपद समय में | [[File:Block graph.svg|thumb|एक [[ब्लॉक ग्राफ|खण्ड लेखाचित्र]], भूगणितीय लेखाचित्र का एक विशेष मामला]] | ||
[[File:Petersen1 tiny.svg|thumb|upright=0.6|[[पीटरसन ग्राफ|पीटरसन लेखाचित्र]], व्यास दो के भूगणितीय ग्राफों में से एक]]यदि किसी लेखाचित्र का प्रत्येक [[द्विसंबद्ध घटक]] भूगणितीय है तो लेखाचित्र स्वयं भूगणितीय है। विशेष रूप से, प्रत्येक खण्ड लेखाचित्र (लेखाचित्र सिद्धांत) भूगणितीय है। {{r|gc}} इसी तरह, क्योंकि एक चक्र लेखाचित्र भूगर्भीय होता है जब इसकी विषम लंबाई होती है, प्रत्येक [[कैक्टस ग्राफ|कैक्टस लेखाचित्र]] जिसमें चक्रों की लंबाई विषम होती है, वह भी भूगणितीय होता है। ये कैक्टस लेखाचित्र ठीक जुड़े हुए लेखाचित्र हैं जिनमें सभी चक्रों की लंबाई विषम होती है। अधिक दृढ़ता से, एक [[ प्लेनर ग्राफ |समतली आलेख]] भूगणितीय है यदि और केवल यदि इसके सभी द्विसंबद्ध घटक या तो विषम-लंबाई वाले चक्र हैं या चार-शीर्ष गुट के भूगणितीय होमोमोर्फिज्म (लेखाचित्र सिद्धांत) हैं।{{r|sw}} | |||
== संगणनात्मक जटिलता == | |||
बहुपद समय में भूगणितीय लेखाचित्र को पहचाना जा सकता है, चौड़ाई की भिन्नता का उपयोग करके पहली खोज जो लेखाचित्र के प्रत्येक शीर्ष से प्रारम्भ होने वाले कई सबसे छोटे पथों का पता लगा सकती है। भूगणितीय लेखाचित्र में एक प्रेरित चार-कोणबिंदु चक्र लेखाचित्र नहीं हो सकता है, न ही एक प्रेरित विषम कोणीय लेखाचित्र, क्योंकि ये दो लेखाचित्र भूगणितीय नहीं हैं। {{r|gc}} विशेष रूप से, विषम कोणीय-मुक्त लेखाचित्र के एक उपसमुच्चय के रूप में, भूगणितीय लेखाचित्र में यह गुण होता है कि प्रत्येक किनारा एक अद्वितीय अधिकतम समूह से संबंधित होता है; इस संदर्भ में अधिकतम गुटों को रेखाएँ भी कहा गया है।{{r|bb}} यह इस प्रकार है कि गुट समस्या, या अधिकतम भारित गुट, सभी अधिकतम गुटों को सूचीबद्ध करके, भूगणितीय लेखाचित्र के लिए बहुपद समय में हल किया जा सकता है। लेखाचित्र का व्यापक वर्ग जिसमें कोई प्रेरित 4-चक्र या विषम कोणीय नहीं है, उसे शक्तिहीन रूप से भूगणितीय कहा जाता है; ये वे लेखाचित्र हैं जहाँ एक दूसरे से ठीक दो दूरी पर स्थित शीर्षों के पास अद्वितीय लघुतम पथ होता है।{{r|gc}} | |||
== व्यास दो == | == व्यास दो == | ||
व्यास दो के | '''व्यास दो के लेखाचित्र के लिए''' (अर्थात, लेखाचित्र जिसमें सभी कोने एक दूसरे से अधिक से अधिक दो दूरी पर हैं), भूगणितीय रेखांकन और शक्तिहीन भूगणितीय रेखांकन मेल खाते हैं। व्यास दो का प्रत्येक भूगणितीय लेखाचित्र तीन प्रकारों में से एक है: | ||
* एक | * एक खण्ड लेखाचित्र जिसमें [[पवनचक्की ग्राफ|पवनचक्की लेखाचित्र]] सहित सभी अधिकतम गुट एक साझा शीर्ष पर जुड़ जाते हैं, | ||
* पैरामीटर के साथ एक [[दृढ़ता से नियमित ग्राफ]] <math>\mu</math> (शीर्षों के प्रत्येक असन्निकट जोड़े के लिए साझा किए गए पड़ोसियों की संख्या) एक के बराबर, या | * पैरामीटर के साथ एक [[दृढ़ता से नियमित ग्राफ|दृढ़ता से नियमित लेखाचित्र]] <math>\mu</math> (शीर्षों के प्रत्येक असन्निकट जोड़े के लिए साझा किए गए पड़ोसियों की संख्या) एक के बराबर, या | ||
* बिल्कुल दो अलग-अलग [[डिग्री (ग्राफ सिद्धांत)]] वाला एक | * बिल्कुल दो अलग-अलग [[डिग्री (ग्राफ सिद्धांत)|डिग्री (लेखाचित्र सिद्धांत)]] वाला एक लेखाचित्र। | ||
दृढ़ता से नियमित | दृढ़ता से नियमित भूगणितीय लेखाचित्र में 5-कोणबिंदु चक्र लेखाचित्र, पीटरसन लेखाचित्र और हॉफ़मैन-सिंगलटन लेखाचित्र शामिल हैं। इस तरह के लेखाचित्र के गुणों पर अतिरिक्त शोध के बावजूद,{{r|bm|df}} यह ज्ञात नहीं है कि इनमें से अधिक लेखाचित्र हैं, या इन लेखाचित्रों में असीम रूप से कई हैं।{{r|bb}} | ||
{{unsolved|mathematics|Are there infinitely many strongly regular geodetic graphs?}} | {{unsolved|mathematics|Are there infinitely many strongly regular geodetic graphs?}} | ||
व्यास दो और दो अलग-अलग डिग्री वाले | व्यास दो और दो अलग-अलग डिग्री वाले भूगणितीय लेखाचित्र में दोनों डिग्री के शीर्षों से बना त्रिभुज नहीं हो सकता है। वे किसी भी Affine समतल (घटना ज्यामिति) #Fineite affine समतल से [[लेवी ग्राफ|लेवी लेखाचित्र]] में जोड़कर निर्मित किए जा सकते हैं। प्रत्येक दो समानांतर रेखाओं के संगत शीर्षों के बीच समतल के अतिरिक्त किनारों के बिंदु-रेखा आपतन लेखाचित्र। तीन समांतर युग्मों में चार बिंदुओं और छह दो-बिंदु रेखाओं वाले बाइनरी एफाइन प्लेन के लिए, इस निर्माण का परिणाम पीटरसन लेखाचित्र है, लेकिन उच्च-क्रम परिमित एफाइन विमानों के लिए यह दो अलग-अलग डिग्री के साथ लेखाचित्र बनाता है। परिमित ज्यामिति से भूगणितीय लेखाचित्र के अन्य संबंधित निर्माण भी ज्ञात हैं, लेकिन यह ज्ञात नहीं है कि ये व्यास दो और दो अलग-अलग डिग्री वाले सभी संभावित भूगणितीय लेखाचित्र को समाप्त करते हैं या नहीं।{{r|bb}} | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 22:24, 10 May 2023
आलेख सिद्धांत में, एक भूगणितीय लेखाचित्र एक अप्रत्यक्ष लेखाचित्र होता है जैसे कि प्रत्येक दो शिखरों के बीच एक अद्वितीय (अभारित) सबसे छोटा पथ उपस्थित होता है।
1962 में ऑयस्टीन अयस्क द्वारा भूगणितीय लेखाचित्र प्रस्तुत किए गए थे, जिन्होंने देखा कि वे तरू की एक विशेषता का सामान्यीकरण करते हैं (जिसमें दूरी की चिंता किए बिना प्रत्येक दो शीर्षों के बीच एक अद्वितीय पथ उपस्थित है), और उनके चित्रण वर्णन के लिए कहा गया। [1] हालांकि इन लेखाचित्रों को बहुपद समय में पहचाना जा सकता है, साठ से अधिक वर्षों के बाद एक पूर्ण लक्षण वर्णन अभी भी दुर्ग्राह्य है।[2]
उदाहरण
हर तरू (लेखाचित्र सिद्धांत),[1] हर पूरा लेखाचित्र,[3] और प्रत्येक विषम-लंबाई चक्र लेखाचित्र भूगणितीय है।[4]
यदि एक भूगणितीय लेखाचित्र है, तो G के प्रत्येक किनारे को उसी विषम लंबाई के पथ से बदलने से एक और भूगणितीय लेखाचित्र उत्पन्न होगा।[5]
पूर्ण लेखाचित्र की स्तिथियों में, पथों द्वारा प्रतिस्थापन का एक अधिक सामान्य प्रतिरूप संभव है: प्रत्येक शीर्ष के लिए एक गैर-ऋणात्मक पूर्णांक चुनें, और इसमें कोने जोड़कर प्रत्येक किनारे को उपविभाजित करें। फिर परिणामी उप-विभाजित पूर्ण लेखाचित्र भूगणितीय है, और प्रत्येक भूगणितीय उप-विभाजित पूर्ण लेखाचित्र इस तरह से प्राप्त किया जा सकता है।[6][7]
संबंधित लेखाचित्र वर्ग
यदि किसी लेखाचित्र का प्रत्येक द्विसंबद्ध घटक भूगणितीय है तो लेखाचित्र स्वयं भूगणितीय है। विशेष रूप से, प्रत्येक खण्ड लेखाचित्र (लेखाचित्र सिद्धांत) भूगणितीय है। [3] इसी तरह, क्योंकि एक चक्र लेखाचित्र भूगर्भीय होता है जब इसकी विषम लंबाई होती है, प्रत्येक कैक्टस लेखाचित्र जिसमें चक्रों की लंबाई विषम होती है, वह भी भूगणितीय होता है। ये कैक्टस लेखाचित्र ठीक जुड़े हुए लेखाचित्र हैं जिनमें सभी चक्रों की लंबाई विषम होती है। अधिक दृढ़ता से, एक समतली आलेख भूगणितीय है यदि और केवल यदि इसके सभी द्विसंबद्ध घटक या तो विषम-लंबाई वाले चक्र हैं या चार-शीर्ष गुट के भूगणितीय होमोमोर्फिज्म (लेखाचित्र सिद्धांत) हैं।[4]
संगणनात्मक जटिलता
बहुपद समय में भूगणितीय लेखाचित्र को पहचाना जा सकता है, चौड़ाई की भिन्नता का उपयोग करके पहली खोज जो लेखाचित्र के प्रत्येक शीर्ष से प्रारम्भ होने वाले कई सबसे छोटे पथों का पता लगा सकती है। भूगणितीय लेखाचित्र में एक प्रेरित चार-कोणबिंदु चक्र लेखाचित्र नहीं हो सकता है, न ही एक प्रेरित विषम कोणीय लेखाचित्र, क्योंकि ये दो लेखाचित्र भूगणितीय नहीं हैं। [3] विशेष रूप से, विषम कोणीय-मुक्त लेखाचित्र के एक उपसमुच्चय के रूप में, भूगणितीय लेखाचित्र में यह गुण होता है कि प्रत्येक किनारा एक अद्वितीय अधिकतम समूह से संबंधित होता है; इस संदर्भ में अधिकतम गुटों को रेखाएँ भी कहा गया है।[8] यह इस प्रकार है कि गुट समस्या, या अधिकतम भारित गुट, सभी अधिकतम गुटों को सूचीबद्ध करके, भूगणितीय लेखाचित्र के लिए बहुपद समय में हल किया जा सकता है। लेखाचित्र का व्यापक वर्ग जिसमें कोई प्रेरित 4-चक्र या विषम कोणीय नहीं है, उसे शक्तिहीन रूप से भूगणितीय कहा जाता है; ये वे लेखाचित्र हैं जहाँ एक दूसरे से ठीक दो दूरी पर स्थित शीर्षों के पास अद्वितीय लघुतम पथ होता है।[3]
व्यास दो
व्यास दो के लेखाचित्र के लिए (अर्थात, लेखाचित्र जिसमें सभी कोने एक दूसरे से अधिक से अधिक दो दूरी पर हैं), भूगणितीय रेखांकन और शक्तिहीन भूगणितीय रेखांकन मेल खाते हैं। व्यास दो का प्रत्येक भूगणितीय लेखाचित्र तीन प्रकारों में से एक है:
- एक खण्ड लेखाचित्र जिसमें पवनचक्की लेखाचित्र सहित सभी अधिकतम गुट एक साझा शीर्ष पर जुड़ जाते हैं,
- पैरामीटर के साथ एक दृढ़ता से नियमित लेखाचित्र (शीर्षों के प्रत्येक असन्निकट जोड़े के लिए साझा किए गए पड़ोसियों की संख्या) एक के बराबर, या
- बिल्कुल दो अलग-अलग डिग्री (लेखाचित्र सिद्धांत) वाला एक लेखाचित्र।
दृढ़ता से नियमित भूगणितीय लेखाचित्र में 5-कोणबिंदु चक्र लेखाचित्र, पीटरसन लेखाचित्र और हॉफ़मैन-सिंगलटन लेखाचित्र शामिल हैं। इस तरह के लेखाचित्र के गुणों पर अतिरिक्त शोध के बावजूद,[9][10] यह ज्ञात नहीं है कि इनमें से अधिक लेखाचित्र हैं, या इन लेखाचित्रों में असीम रूप से कई हैं।[8]
Are there infinitely many strongly regular geodetic graphs?
व्यास दो और दो अलग-अलग डिग्री वाले भूगणितीय लेखाचित्र में दोनों डिग्री के शीर्षों से बना त्रिभुज नहीं हो सकता है। वे किसी भी Affine समतल (घटना ज्यामिति) #Fineite affine समतल से लेवी लेखाचित्र में जोड़कर निर्मित किए जा सकते हैं। प्रत्येक दो समानांतर रेखाओं के संगत शीर्षों के बीच समतल के अतिरिक्त किनारों के बिंदु-रेखा आपतन लेखाचित्र। तीन समांतर युग्मों में चार बिंदुओं और छह दो-बिंदु रेखाओं वाले बाइनरी एफाइन प्लेन के लिए, इस निर्माण का परिणाम पीटरसन लेखाचित्र है, लेकिन उच्च-क्रम परिमित एफाइन विमानों के लिए यह दो अलग-अलग डिग्री के साथ लेखाचित्र बनाता है। परिमित ज्यामिति से भूगणितीय लेखाचित्र के अन्य संबंधित निर्माण भी ज्ञात हैं, लेकिन यह ज्ञात नहीं है कि ये व्यास दो और दो अलग-अलग डिग्री वाले सभी संभावित भूगणितीय लेखाचित्र को समाप्त करते हैं या नहीं।[8]
संदर्भ
- ↑ 1.0 1.1 Ore, Øystein (1962), Theory of Graphs, Colloquium Publications, vol. 38, Providence, Rhode Island: American Mathematical Society, p. 104, ISBN 9780821810385, MR 0150753
- ↑ Cornelsen, Sabine; Pfister, Maximilian; Förster, Henry; Gronemann, Martin; Hoffmann, Michael; Kobourov, Stephen; Schneck, Thomas (2020), "Drawing shortest paths in geodetic graphs", Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization, arXiv:2008.07637
- ↑ 3.0 3.1 3.2 3.3 "Geodetic graphs", Information System on Graph Classes and their Inclusions, retrieved 2020-09-14
- ↑ 4.0 4.1 Stemple, Joel G.; Watkins, Mark E. (1968), "On planar geodetic graphs", Journal of Combinatorial Theory, 4 (2): 101–117, doi:10.1016/S0021-9800(68)80035-3, MR 0218267
- ↑ Parthasarathy, K. R.; Srinivasan, N. (1982), "Some general constructions of geodetic blocks", Journal of Combinatorial Theory, Series B, 33 (2): 121–136, doi:10.1016/0095-8956(82)90063-6, MR 0685061
- ↑ Plesník, Ján (1977), "Two constructions of geodetic graphs", Mathematica Slovaca, 27 (1): 65–71, MR 0460179
- ↑ Stemple, Joel G. (1979), "Geodetic graphs homeomorphic to a complete graph", Second International Conference on Combinatorial Mathematics (New York, 1978), Annals of the New York Academy of Sciences, vol. 319, pp. 512–517, doi:10.1111/j.1749-6632.1979.tb32829.x, MR 0556062
- ↑ 8.0 8.1 8.2 Blokhuis, A.; Brouwer, A. E. (1988), "Geodetic graphs of diameter two", Geometriae Dedicata, 25 (1–3): 527–533, doi:10.1007/BF00191941, MR 0925851, S2CID 189890651
- ↑ Belousov, I. N.; Makhnev, A. A. (2006), "On strongly regular graphs with and their automorphisms", Doklady Akademii Nauk, 410 (2): 151–155, MR 2455371
- ↑ Deutsch, J.; Fisher, P. H. (2001), "On strongly regular graphs with ", European Journal of Combinatorics, 22 (3): 303–306, doi:10.1006/eujc.2000.0472, MR 1822718
