जियोडेटिक ग्राफ
ग्राफ़ थ्योरी में, एक जियोडेटिक ग्राफ़ एक अप्रत्यक्ष ग्राफ़ होता है जैसे कि प्रत्येक दो शिखरों के बीच एक अद्वितीय (अभारित) सबसे छोटा पथ मौजूद होता है।
1962 में Øystein Ore द्वारा जिओडेटिक ग्राफ पेश किए गए थे, जिन्होंने देखा कि वे पेड़ों की एक संपत्ति का सामान्यीकरण करते हैं (जिसमें दूरी की परवाह किए बिना प्रत्येक दो शीर्षों के बीच एक अद्वितीय पथ मौजूद है), और उनके लक्षण वर्णन के लिए कहा।[1] हालांकि इन ग्राफ़ों को बहुपद समय में पहचाना जा सकता है, साठ से अधिक वर्षों के बाद एक पूर्ण लक्षण वर्णन अभी भी मायावी है।[2]
उदाहरण
हर पेड़ (ग्राफ सिद्धांत),[1] हर पूरा ग्राफ,[3] और प्रत्येक विषम-लंबाई चक्र ग्राफ जियोडेटिक है।[4]
अगर एक जियोडेटिक ग्राफ है, फिर इसके हर किनारे को बदल देता है उसी विषम लंबाई के पथ से एक और भूगणितीय ग्राफ का निर्माण होगा।[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
