Lattice graph
ग्राफ सिद्धांत में, एक जाली ग्राफ, जाली ग्राफ, या ग्रिड ग्राफ एक ग्राफ है जिसका चित्र, कुछ यूक्लिडियन स्थान में एम्बेडेड, एक नियमित टाइलिंग बनाता है। इसका तात्पर्य यह है कि विषयगत परिवर्तनों का समूह जो ग्राफ को अपने पास भेजता है, वह समूह-सैद्धांतिक अर्थ में एक जाली है। आमतौर पर, ग्राफ सिद्धांत के अधिक अमूर्त अर्थ में इस तरह के ग्राफ और अंतरिक्ष में इसके चित्र (अक्सर समतल या 3डी स्थान) के बीच कोई स्पष्ट अंतर नहीं किया जाता है। इस प्रकार के ग्राफ को जल्द ही केवल जाली, जाली या ग्रिड कहा जा सकता है। इसके अलावा, इन शब्दों का उपयोग आमतौर पर अनंत ग्राफ के एक सीमित खंड के लिए भी किया जाता है, जैसा कि "8 × 8 वर्ग ग्रिड" में होता है। जाली ग्राफ शब्द को साहित्य में कुछ नियमित संरचना वाले विभिन्न अन्य प्रकार के ग्राफों के लिए भी दिया गया है, जैसे कि कई पूर्ण ग्राफों का कार्टेशियन उत्पाद। वर्ग ग्रिड ग्राफ एक सामान्य प्रकार का जाली ग्राफ (जिसे विभिन्न नामों के तहत जाना जाता है, जैसे कि वर्ग ग्रिड ग्राफ) वह ग्राफ है जिसके शीर्ष पूर्णांक निर्देशांक के साथ समतल में बिंदुओं के अनुरूप होते हैं, जो सीमा में होते हैं, सीमा में होते हैं, और जब भी संबंधित बिंदु 1 की दूरी पर होते हैं तो दो शीर्ष एक किनारे से जुड़े होते हैं। दूसरे शब्दों में, यह वर्णित बिंदु समुच्चय के लिए एक इकाई दूरी ग्राफ है। एक वर्ग ग्रिड ग्राफ ग्राफ का एक कार्टेशियन उत्पाद है, अर्थात्, n-1 और m-1 किनारों वाले दो पथ ग्राफ का। चूँकि पथ ग्राफ एक मध्यक ग्राफ है, बाद वाले तथ्य का तात्पर्य है कि वर्ग ग्रिड ग्राफ भी एक मध्यक ग्राफ है। सभी वर्गाकार ग्रिड ग्राफ द्विदलीय होते हैं, जिन्हें आसानी से इस तथ्य से सत्यापित किया जाता है कि कोई भी चेकरबोर्ड शैली में शीर्षों को रंग सकता है। एक पथ ग्राफ को ग्रिड n गुना 1 पर एक ग्रिड ग्राफ भी माना जा सकता है। 2×2 ग्रिड ग्राफ एक 4-चक्र है। प्रत्येक समतलीय ग्राफ एच, एच × एच ग्रिड का एक लघु है, जहाँ। ग्रिड बहिष्करण प्रमेय के कारण ग्रिड ग्राफ लघु ग्राफ के सिद्धांत में मौलिक वस्तुएं हैं। वे द्वि-आयामी सिद्धांत में एक प्रमुख भूमिका निभाते हैं। अन्य प्रकार एक त्रिकोणीय ग्रिड ग्राफ एक ग्राफ है जो एक त्रिकोणीय ग्रिड से मेल खाता है। समतल में बिंदुओं के एक सीमित समूह के लिए एक हनान ग्रिड ग्राफ सेट के प्रत्येक बिंदु के माध्यम से सभी ऊर्ध्वाधर और क्षैतिज रेखाओं के प्रतिच्छेदन द्वारा प्राप्त ग्रिड द्वारा उत्पादित किया जाता है। रुक का ग्राफ (वह ग्राफ जो शतरंज की बिसात पर रुक शतरंज के टुकड़े की सभी कानूनी चालों का प्रतिनिधित्व करता है) को कभी-कभी जाली ग्राफ भी कहा जाता है, हालांकि यह ग्राफ इस लेख में वर्णित जाली ग्राफ से बिल्कुल अलग है। परी शतरंज के टुकड़े वज़ीर की वैध चालें वर्गाकार जाली ग्राफ बनाती हैं। लैटिस पाथ पिक की प्रमेय पूर्णांक त्रिभुज को 2डी लैटिस में भी देखें नियमित ग्राफ संदर्भ योजना ग्राफ ग्राफ परिवार