लेवी ग्राफ
| Levi graph | |
|---|---|
 The Pappus graph, a Levi graph with 18 vertices formed from the Pappus configuration. Vertices labeled with single letters correspond to points in the configuration; vertices labeled with three letters correspond to lines through three points. | |
| Girth | ≥ 6 |
| Table of graphs and parameters | |
साहचर्य में, एक लेवी ग्राफ या घटना ग्राफ एक द्विदलीय ग्राफ है जो एक घटना संरचना से जुड़ा होता है।[1][2] एक घटना ज्यामिति या एक प्रक्षेपी विन्यास में बिंदुओं और रेखाओं के संग्रह से, हम एक शीर्ष प्रति बिंदु, एक शीर्ष प्रति पंक्ति और एक बिंदु और एक रेखा के बीच प्रत्येक घटना के लिए एक किनारे के साथ एक ग्राफ बनाते हैं। उनका नाम फ्रेडरिक विल्हेम लेवी के नाम पर रखा गया है, जिन्होंने 1942 में उनके बारे में लिखा था।[1][3] बिंदुओं और रेखाओं की एक प्रणाली के लेवी ग्राफ में आमतौर पर कम से कम छः गर्थ (ग्राफ सिद्धांत) होते हैं: कोई भी 4-चक्र ग्राफ समान दो बिंदुओं के माध्यम से दो पंक्तियों के अनुरूप होगा। इसके विपरीत किसी भी द्विदलीय ग्राफ को कम से कम छह परिधि के साथ एक अमूर्त घटना संरचना के लेवी ग्राफ के रूप में देखा जा सकता है।[1]कॉन्फ़िगरेशन के लेवी ग्राफ़ बिरेगुलर ग्राफ हैं, और कम से कम छह परिधि वाले प्रत्येक बायरेगुलर ग्राफ़ को एक अमूर्त कॉन्फ़िगरेशन के लेवी ग्राफ़ के रूप में देखा जा सकता है।[4] लेवी ग्राफ को अन्य प्रकार की घटना संरचना के लिए भी परिभाषित किया जा सकता है, जैसे कि यूक्लिडियन अंतरिक्ष में बिंदुओं और विमानों के बीच की घटनाएं। प्रत्येक लेवी ग्राफ के लिए एक समान hypergraph होता है, और इसके विपरीत।
उदाहरण
Vertex 3 is part of the circular edge (3, 5, 6), the diagonal edge (3, 7, 4), and the side edge (1, 3, 2).
- Desargues ग्राफ़ Desargues कॉन्फ़िगरेशन का लेवी ग्राफ़ है, जो 10 बिंदुओं और 10 रेखाओं से बना है। प्रत्येक रेखा पर 3 बिंदु होते हैं, और प्रत्येक बिंदु से होकर 3 रेखाएँ गुजरती हैं। Desargues ग्राफ को सामान्यीकृत पीटरसन ग्राफ G(10,3) या पैरामीटर 5,2 के साथ Kneser ग्राफ के रूप में भी देखा जा सकता है। यह 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.
