जियोडेटिक ग्राफ
आलेख सिद्धांत में, एक भूगणितीय लेखाचित्र एक अप्रत्यक्ष लेखाचित्र होता है जैसे कि प्रत्येक दो शिखरों के बीच एक अद्वितीय (अभारित) सबसे छोटा पथ उपस्थित होता है।
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?
दो व्यास और दो अलग-अलग घात वाले भूगणितीय लेखाचित्र में दोनों घात के शीर्षों से बना त्रिभुज नहीं हो सकता है। प्रत्येक दो समानांतर रेखाओं के संगत शीर्षों के बीच समतल के बिंदु-रेखा आपतन लेखाचित्र में अतिरिक्त किनारों को जोड़कर किसी भी परिमित संबंध तल से उनका निर्माण किया जा सकता है।। तीन समांतर युग्मों में चार बिंदुओं और छह दो-बिंदु रेखाओं वाले युग्मक सजातीय तल के लिए, इस निर्माण का परिणाम पीटरसन लेखाचित्र है, लेकिन उच्च-क्रम परिमित सजातीय तल के लिए यह दो अलग-अलग घात के साथ लेखाचित्र बनाता है। परिमित ज्यामिति से भूगणितीय लेखाचित्र के अन्य संबंधित निर्माण भी ज्ञात हैं, लेकिन यह ज्ञात नहीं है कि ये दो व्यास और दो अलग-अलग घात वाले सभी संभावित भूगणितीय लेखाचित्र को समाप्त करते हैं या नहीं।[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
