शून्य-भाजक ग्राफ

शून्य-भाजक ग्राफ $\mathbb {Z} _{2}\times \mathbb {Z} _{4}$, एकमात्र संभावित शून्य-भाजक ग्राफ जो पेड़ है लेकिन तारा नहीं है

गणित में, और विशेष रूप से संयोजक क्रमविनिमेय बीजगणित में, शून्य-भाजक ग्राफ अप्रत्यक्ष ग्राफ है जो क्रमविनिमेय वलय के शून्य भाजक का प्रतिनिधित्व करता है। इसमें वलय के तत्व इसके शीर्ष (ग्राफ़ सिद्धांत) के रूप में हैं, और तत्वों के जोड़े जिनका उत्पाद शून्य है, इसके किनारे (ग्राफ़ सिद्धांत) के रूप में हैं।

परिभाषा

आमतौर पर उपयोग किए जाने वाले शून्य-भाजक ग्राफ के दो रूप हैं। की मूल परिभाषा में Beck (1988), शीर्ष वलय के सभी तत्वों का प्रतिनिधित्व करते हैं। बाद के संस्करण में अध्ययन किया गया Anderson & Livingston (1999), शीर्ष दिए गए रिंग के केवल शून्य विभाजक का प्रतिनिधित्व करते हैं।

उदाहरण

अगर $n$ [[अर्ध अभाज्य संख्या]] है (दो अभाज्य संख्याओं का गुणनफल) फिर पूर्णांक मॉड्यूलो की रिंग का शून्य-भाजक ग्राफ $n$ (इसके शीर्षों के रूप में केवल शून्य भाजक के साथ) या तो पूर्ण ग्राफ़ या पूर्ण द्विदलीय ग्राफ़ है। यह संपूर्ण ग्राफ़ है $K_{p-1}$ उस मामले में $n=p^{2}$ कुछ अभाज्य संख्या के लिए $p$. इस मामले में शीर्ष सभी शून्येतर गुणज हैं $p$, और इनमें से किन्हीं दो संख्याओं का गुणनफल 0 मॉड्यूलो है $p^{2}$.

यह पूर्ण द्विदलीय ग्राफ है $K_{p-1,q-1}$ उस मामले में $n=pq$ दो अलग-अलग अभाज्य संख्याओं के लिए $p$ और $q$. द्विविभाजन के दो पक्ष हैं $p-1$ के शून्येतर गुणज $q$ और यह $q-1$ के शून्येतर गुणज $p$, क्रमश। दो संख्याएँ (जो स्वयं शून्य मॉड्यूलो नहीं हैं $n$) शून्य मॉड्यूलो से गुणा करें $n$ यदि और केवल यदि का गुणज है $p$ और दूसरा का गुणज है $q$, इसलिए इस ग्राफ़ में द्विविभाजन के विपरीत पक्षों पर शीर्षों की प्रत्येक जोड़ी के बीच किनारा है, और कोई अन्य किनारा नहीं है। अधिक सामान्यतः, शून्य-भाजक ग्राफ किसी भी रिंग के लिए पूर्ण द्विदलीय ग्राफ है जो दो अभिन्न डोमेन का उत्पाद रिंग है।

एकमात्र चक्र ग्राफ़ जिन्हें शून्य-उत्पाद ग्राफ़ (शीर्ष के रूप में शून्य विभाजक के साथ) के रूप में महसूस किया जा सकता है, लंबाई 3 या 4 के चक्र हैं। एकमात्र वृक्ष (ग्राफ़ सिद्धांत) जिसे शून्य-विभाजक ग्राफ़ के रूप में महसूस किया जा सकता है, वह है तारा (ग्राफ़ सिद्धांत) (पूर्ण द्विदलीय ग्राफ़ जो कि पेड़ हैं) और शून्य-भाजक ग्राफ़ के रूप में गठित पांच-शीर्ष वृक्ष हैं $\mathbb {Z} _{2}\times \mathbb {Z} _{4}$.

गुण

ग्राफ़ के उस संस्करण में जिसमें सभी तत्व शामिल हैं, 0 सार्वभौमिक शीर्ष है, और शून्य विभाजक को उन शीर्षों के रूप में पहचाना जा सकता है जिनका 0 के अलावा कोई पड़ोसी है। क्योंकि इसमें सार्वभौमिक शीर्ष है, सभी रिंग तत्वों का ग्राफ़ हमेशा जुड़ा रहता है और इसका व्यास अधिकतम दो होता है। सभी शून्य विभाजकों का ग्राफ प्रत्येक रिंग के लिए गैर-रिक्त है जो अभिन्न डोमेन नहीं है। यह जुड़ा रहता है, इसका व्यास अधिकतम तीन है, और (यदि इसमें चक्र है) अधिकतम चार पर परिधि (ग्राफ़ सिद्धांत) है।

एक वलय का शून्य-भाजक ग्राफ जो अभिन्न डोमेन नहीं है, परिमित है यदि और केवल यदि वलय परिमित है। अधिक ठोस रूप से, यदि ग्राफ़ में अधिकतम डिग्री है $d$, अंगूठी अधिक से अधिक है $(d^{2}-2d+2)^{2}$ तत्व. यदि वलय और ग्राफ अनंत हैं, तो प्रत्येक किनारे का समापन बिंदु होता है जिसमें अनंत कई पड़ोसी होते हैं।

Beck (1988) अनुमान लगाया गया कि (पूर्ण ग्राफ़ की तरह) शून्य-भाजक ग्राफ़ में हमेशा समान क्लिक संख्या और रंगीन संख्या होती है। वैसे यह सत्य नहीं है; द्वारा प्रतिउदाहरण की खोज की गई थी Anderson & Naseer (1993).