लेवी ग्राफ

लेवी ग्राफ
पप्पस ग्राफ, पप्पस विन्यास से बने 18 शीर्षों के साथ एक लेवी ग्राफ। एकल अक्षरों से लेबल किए गए शीर्ष विन्यास में बिंदुओं के अनुरूप होते हैं; तीन अक्षरों से लेबल किए गए शीर्ष तीन बिंदुओं से होकर जाने वाली रेखाओं के अनुरूप होते हैं।
Girth	≥ 6
Table of graphs and parameters

मिश्रित गणित में, लेवी ग्राफ या आपतन ग्राफ एक द्विपक्षीय ग्राफ है जो आपतन संरचना से जुड़ा होता है। आपतन ज्यामिति या प्रक्षेपी विन्यास में बिंदुओं और रेखाओं के संग्रह से, हम कोणबिंदु प्रति बिंदु, कोणबिंदु प्रति पंक्ति और बिंदु और रेखा के बीच प्रत्येक आपतन के लिए एक किनारे के साथ ग्राफ बनाते हैं। उनका नाम फ्रेडरिक विल्हेम लेवी के नाम पर रखा गया है, जिन्होंने 1942 में उनके बारे में लिखा था।

बिंदुओं और रेखाओं की एक प्रणाली के लेवी ग्राफ में सामान्यतः कम से कम छः परिधि (ग्राफ सिद्धांत) होते हैं: कोई भी 4-चक्र ग्राफ समान दो बिंदुओं के माध्यम से दो पंक्तियों के अनुरूप होगा। इसके विपरीत किसी भी द्विपक्षीय ग्राफ को कम से कम छह परिधि के साथ अमूर्त आपतन संरचना के लेवी ग्राफ के रूप में देखा जा सकता है। विन्यास के लेवी ग्राफ़ बिरेगुलर ग्राफ हैं, और कम से कम छह परिधि वाले प्रत्येक बायरेगुलर ग्राफ़ को अमूर्त विन्यास के लेवी ग्राफ़ के रूप में देखा जा सकता है।

लेवी ग्राफ को अन्य प्रकार की आपतन संरचना के लिए भी परिभाषित किया जा सकता है, जैसे कि यूक्लिडियन समष्टि में बिंदुओं और समतलो के बीच की आपतनएं है। प्रत्येक लेवी ग्राफ के लिए, समतुल्य हाइपरग्राफ है, और इसके विपरीत है।

उदाहरण

Heawood graph and Fano plane
Vertex 3 is part of the circular edge (3, 5, 6), the diagonal edge (3, 7, 4), and the side edge (1, 3, 2).

• डेसरग्यूज़ ग्राफ डेसरग्यूज़ विन्यास का लेवी ग्राफ है, जो 10 बिंदुओं और 10 लाइनों से बना है। प्रत्येक लाइन पर 3 बिंदु हैं, और प्रत्येक बिंदु से गुजरने वाली 3 रेखाएं हैं। डेसरग्यूज़ ग्राफ को सामान्यीकृत पीटरसन ग्राफ G(10,3) या पैरामीटर 5,2 के साथ केनेसर ग्राफ के रूप में भी देखा जा सकता है। यह 20 कोने के साथ 3-समभुजकोणीय है।
• हीवुड ग्राफ फानो समतल का लेवी ग्राफ है। इसे (3,6)-कैज (ग्राफ़ सिद्धांत) के रूप में भी जाना जाता है, और यह 14 शीर्षों के साथ 3-समभुजकोणीय है।
• मोबियस-कैंटर ग्राफ मोबियस-कैंटर विन्यास का लेवी ग्राफ है, जो 8 बिंदुओं और 8 रेखाओं की एक प्रणाली है जिसे यूक्लिडियन समष्टि में सीधी रेखाओं द्वारा सिद्ध नहीं किया जा सकता है। यह 16 शीर्षों के साथ 3-समभुजकोणीय है।
• पाप्पस ग्राफ, पप्पस विन्यास का लेवी ग्राफ है, जो 9 बिंदुओं और 9 रेखाओं से बना है। डेसरग्यूज़ विन्यास की तरह प्रत्येक पंक्ति पर 3 बिंदु हैं और प्रत्येक बिंदु से गुजरने वाली 3 पंक्तियाँ हैं। यह 18 शीर्षों के साथ 3-समभुजकोणीय है।
• ग्रे ग्राफ पाप्पस विन्यास का लेवी ग्राफ है जिसे $\mathbb {R} ^{3}$ के तौर पर $3\times 3\times 3$ 27 बिंदुओं का ग्रिड और उनके माध्यम से 27 आयतीय रेखाएँ के द्वारा सिद्ध किया जा सकता है।
• ट्यूट आठ-कैज क्रेमोना-रिचमंड विन्यास का लेवी ग्राफ है। इसे (3,8)-कैज के रूप में भी जाना जाता है, और यह 30 कोने के साथ 3-समभुजकोणीय है।
• चार आयामी हाइपरक्यूब ग्राफ $Q_{4}$ दो आपस में आपतित टेट्राहेड्रा के बिंदुओं और तलों द्वारा गठित मोबियस विन्यास का लेवी ग्राफ है।
• 112 शीर्षों पर लजुब्जाना ग्राफ लजुब्जाना विन्यास का लेवी ग्राफ है।

बाहरी संबंध

• Weisstein, Eric W. "Levi Graph". MathWorld.