लेवी ग्राफ
लेवी ग्राफ | |
---|---|
Girth | ≥ 6 |
Table of graphs and parameters |
मिश्रित गणित में, लेवी ग्राफ या आपतन ग्राफ एक द्विपक्षीय ग्राफ है जो आपतन संरचना से जुड़ा होता है।[1][2] आपतन ज्यामिति या प्रक्षेपी विन्यास में बिंदुओं और रेखाओं के संग्रह से, हम कोणबिंदु प्रति बिंदु, कोणबिंदु प्रति पंक्ति और बिंदु और रेखा के बीच प्रत्येक आपतन के लिए एक किनारे के साथ एक ग्राफ बनाते हैं। उनका नाम फ्रेडरिक विल्हेम लेवी के नाम पर रखा गया है, जिन्होंने 1942 में उनके बारे में लिखा था।[1][3]
बिंदुओं और रेखाओं की एक प्रणाली के लेवी ग्राफ में सामान्यतः कम से कम छः परिधि (ग्राफ सिद्धांत) होते हैं: कोई भी 4-चक्र ग्राफ समान दो बिंदुओं के माध्यम से दो पंक्तियों के अनुरूप होगा। इसके विपरीत किसी भी द्विपक्षीय ग्राफ को कम से कम छह परिधि के साथ अमूर्त आपतन संरचना के लेवी ग्राफ के रूप में देखा जा सकता है।[1] कॉन्फ़िगरेशन के लेवी ग्राफ़ बिरेगुलर ग्राफ हैं, और कम से कम छह परिधि वाले प्रत्येक बायरेगुलर ग्राफ़ को एक अमूर्त कॉन्फ़िगरेशन के लेवी ग्राफ़ के रूप में देखा जा सकता है।[4]
लेवी ग्राफ को अन्य प्रकार की आपतन संरचना के लिए भी परिभाषित किया जा सकता है, जैसे कि यूक्लिडियन समष्टि में बिंदुओं और समतलो के बीच की आपतनएं है। प्रत्येक लेवी ग्राफ के लिए, समतुल्य हाइपरग्राफ है, और इसके विपरीत है।
उदाहरण
- डेसरग्यूज़ ग्राफ डेसरग्यूज़ विन्यास का लेवी ग्राफ है, जो 10 बिंदुओं और 10 लाइनों से बना है। प्रत्येक लाइन पर 3 बिंदु हैं, और प्रत्येक बिंदु से गुजरने वाली 3 रेखाएं हैं। डेसरग्यूज़ ग्राफ को सामान्यीकृत पीटरसन ग्राफ G(10,3) या पैरामीटर 5,2 के साथ केनेसर ग्राफ के रूप में भी देखा जा सकता है। यह 20 कोने के साथ 3-समभुजकोणीय है।
- हीवुड ग्राफ फानो विमान का लेवी ग्राफ है। इसे (3,6)-पिंजरे (ग्राफ़ सिद्धांत) के रूप में भी जाना जाता है, और यह 14 शीर्षों के साथ 3-नियमित है।
- मोबियस-कैंटर ग्राफ मोबियस-कैंटर कॉन्फ़िगरेशन का लेवी ग्राफ है, जो 8 बिंदुओं और 8 रेखाओं की एक प्रणाली है जिसे यूक्लिडियन विमान में सीधी रेखाओं द्वारा महसूस नहीं किया जा सकता है। यह 16 शीर्षों के साथ 3-नियमित है।
- पप्पू ग्राफ, पप्पस विन्यास का लेवी ग्राफ है, जो 9 बिंदुओं और 9 रेखाओं से बना है। Desargues कॉन्फ़िगरेशन की तरह प्रत्येक पंक्ति पर 3 बिंदु हैं और प्रत्येक बिंदु से गुजरने वाली 3 पंक्तियाँ हैं। यह 18 शीर्षों के साथ 3-नियमित है।
- ग्रे ग्राफ पप्पू विन्यास का लेवी ग्राफ है जिसे महसूस किया जा सकता है के तौर पर 27 बिंदुओं का ग्रिड और उनके माध्यम से 27 ओर्थोगोनल रेखाएँ।
- टुट्टे आठ-पिंजरा क्रेमोना-रिचमंड कॉन्फ़िगरेशन का लेवी ग्राफ है। इसे (3,8)-पिंजरे के रूप में भी जाना जाता है, और यह 30 कोने के साथ 3-नियमित है।
- चार आयामी हाइपरक्यूब ग्राफ दो आपस में आपतित टेट्राहेड्रा के बिंदुओं और तलों द्वारा गठित मोबियस विन्यास का लेवी ग्राफ है।
- 112 शीर्षों पर लजुब्जाना ग्राफ लजुब्जाना विन्यास का लेवी ग्राफ है।[5]
संदर्भ
- ↑ 1.0 1.1 1.2 Grünbaum, Branko (2006), "Configurations of points and lines", The Coxeter Legacy, Providence, RI: American Mathematical Society, pp. 179–225, MR 2209028. See in particular p. 181.
- ↑ Polster, Burkard (1998), A Geometrical Picture Book, Universitext, New York: Springer-Verlag, p. 5, doi:10.1007/978-1-4419-8526-2, ISBN 0-387-98437-2, MR 1640615.
- ↑ Levi, F. W. (1942), Finite Geometrical Systems, Calcutta: University of Calcutta, MR 0006834.
- ↑ Gropp, Harald (2007), "VI.7 Configurations", in Colbourn, Charles J.; Dinitz, Jeffrey H. (eds.), Handbook of combinatorial designs, Discrete Mathematics and its Applications (Boca Raton) (Second ed.), Chapman & Hall/CRC, Boca Raton, Florida, pp. 353–355.
- ↑ Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Pisanski, Tomaž; Potočnik, Primož (2002), The Ljubljana Graph (PDF), IMFM Preprint 40-845, University of Ljubljana Department of Mathematics.