शून्य-भाजक ग्राफ: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Graph of zero divisors of a commutative ring}}
{{Short description|Graph of zero divisors of a commutative ring}}
[[File:Zero-divisor graph of Z2xZ4.svg|thumb|शून्य-भाजक ग्राफ <math>\mathbb{Z}_2\times\mathbb{Z}_4</math>, एकमात्र संभावित शून्य-भाजक ग्राफ जो पेड़ है लेकिन तारा नहीं है]]गणित में, और विशेष रूप से संयोजक क्रमविनिमेय बीजगणित में, शून्य-भाजक ग्राफ [[अप्रत्यक्ष ग्राफ]] है जो [[क्रमविनिमेय वलय]] के [[शून्य भाजक]] का प्रतिनिधित्व करता है। इसमें वलय के तत्व इसके [[शीर्ष (ग्राफ़ सिद्धांत)]] के रूप में हैं, और तत्वों के जोड़े जिनका उत्पाद शून्य है, इसके किनारे (ग्राफ़ सिद्धांत) के रूप में हैं।{{r|aas}}
[[File:Zero-divisor graph of Z2xZ4.svg|thumb|शून्य-भाजक ग्राफ <math>\mathbb{Z}_2\times\mathbb{Z}_4</math>, एकमात्र संभावित शून्य-भाजक ग्राफ जो पेड़ है लेकिन तारा नहीं है]]गणित और विशेष रूप से संयोजक क्रमविनिमेय बीजगणित में '''शून्य-भाजक ग्राफ''' ऐसा [[अप्रत्यक्ष ग्राफ]] है, जो [[क्रमविनिमेय वलय]] के [[शून्य भाजक]] से प्राप्त होने वाले विभिन्न मानों का प्रतिनिधित्व करता है। इसमें वलय के विभिन्न तत्वों को इसके [[शीर्ष (ग्राफ़ सिद्धांत)|ग्राफ़ सिद्धांत]] के अनुसार प्राप्त होने वाले [[शीर्ष (ग्राफ़ सिद्धांत)|शीर्ष]] मानों के रूप में उपयोग किया जाता हैं, और इसके पश्चात इन तत्वों के संयुग्मों को जिनका उत्पाद शून्य से किया जाता है, इसके विभिन्न किनारों पर ग्राफ़ सिद्धांत का उपयोग करके इसके मौलिक रूप में प्रयुक्त होता हैं।{{r|aas}}


==परिभाषा==
==परिभाषा==
आमतौर पर उपयोग किए जाने वाले शून्य-भाजक ग्राफ के दो रूप हैं।
सामान्यतः उपयोग किए जाने वाले इस प्रकार के शून्य-भाजक ग्राफ के मूलतः दो रूप होते हैं। जिसमें इसकी मूल परिभाषा में {{harvtxt|बेक|1988}} के नियम द्वारा इसके शीर्ष वलय के सभी तत्वों का प्रतिनिधित्व किया जाता हैं।{{r|beck}} इसके पश्चात इसके संस्करण में अध्ययन किये जाने वाले {{harvtxt|एंडर्सन|लिविंगस्टन|1999}}, के  द्वारा इसके शीर्ष पर दिए गए वलय के केवल शून्य विभाजक का प्रतिनिधित्व किया जाता हैं।{{r|al}}
की मूल परिभाषा में {{harvtxt|Beck|1988}}, शीर्ष वलय के सभी तत्वों का प्रतिनिधित्व करते हैं।{{r|beck}} बाद के संस्करण में अध्ययन किया गया {{harvtxt|Anderson|Livingston|1999}}, शीर्ष दिए गए रिंग के केवल शून्य विभाजक का प्रतिनिधित्व करते हैं।{{r|al}}


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


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


एकमात्र [[चक्र ग्राफ]]जिन्हें शून्य-उत्पाद ग्राफ़ (शीर्ष के रूप में शून्य विभाजक के साथ) के रूप में महसूस किया जा सकता है, लंबाई 3 या 4 के चक्र हैं।{{r|al}}
यह पूर्ण द्विदलीय ग्राफ <math>K_{p-1,q-1}</math> है, इस स्थिति में <math>n=pq</math> को दो अलग-अलग अभाज्य संख्याओं के लिए <math>p</math> और <math>q</math> द्वारा विभाजित किया जाता हैं। इस प्रकार द्वि-विभाजन के दो पक्ष हैं, जहां पर <math>p-1</math> के शून्येतर गुणज <math>q</math> और यह <math>q-1</math> के शून्येतर गुणज <math>p</math> है। जो इन दोनो संख्याओं को जो स्वयं शून्य <math>n</math> का प्रारूप नहीं हैं, इसलिए शून्य प्रारूप <math>n</math> से गुणा करने पर यदि इसका गुणज  <math>p</math> प्राप्त होता है, और दूसरा का गुणज <math>q</math> प्राप्त होता है, इस कारण इस ग्राफ़ में द्विविभाजन के विपरीत पक्षों पर शीर्षों के प्रत्येक संयोजन के बीच के किनारे का रूप प्रदर्शित होता है, और इस प्रकार इसका कोई अन्य किनारा नहीं है। इस कारण अधिकांशतः सामान्य रूप से शून्य-भाजक ग्राफ किसी भी वलय के लिए पूर्ण द्विदलीय ग्राफ है, जो दो [[अभिन्न डोमेन]] के विभिन्न उत्पादों का वलय है।{{r|al}}
एकमात्र वृक्ष (ग्राफ़ सिद्धांत) जिसे शून्य-विभाजक ग्राफ़ के रूप में महसूस किया जा सकता है, वह है तारा (ग्राफ़ सिद्धांत) (पूर्ण द्विदलीय ग्राफ़ जो कि पेड़ हैं) और शून्य-भाजक ग्राफ़ के रूप में गठित पांच-शीर्ष वृक्ष हैं <math>\mathbb{Z}_2\times\mathbb{Z}_4</math>.{{r|aas|al}}
 
एकमात्र [[चक्र ग्राफ]] जिन्हें शून्य-उत्पाद ग्राफ़ अर्ताथ शीर्ष के रूप में शून्य विभाजक के साथ इसके विभिन्न रूपों में देखा जा सकता है, जिसकी लंबाई 3 या 4 चक्रों के समान हैं।{{r|al}}  
 
एकमात्र ट्री ग्राफ़ सिद्धांत जिसे शून्य-विभाजक ग्राफ़ के रूप में देखा जा सकता है, वह है स्टार ग्राफ़ सिद्धांत, जो पूर्ण रूप से द्विदलीय ग्राफ़ के रूप में प्रदर्शित होता हैं जो ट्री ग़्राफ सिद्धांत का स्वरूप हैं, और शून्य-भाजक ग्राफ़ के रूप में गठित पांच-शीर्ष ट्री <math>\mathbb{Z}_2\times\mathbb{Z}_4</math> हैं।{{r|aas|al}}


==गुण==
==गुण==
ग्राफ़ के उस संस्करण में जिसमें सभी तत्व शामिल हैं, 0 [[सार्वभौमिक शीर्ष]] है, और शून्य विभाजक को उन शीर्षों के रूप में पहचाना जा सकता है जिनका 0 के अलावा कोई पड़ोसी है।
इस ग्राफ़ के उचित संस्करण में जिसमें सभी तत्व इसमें सम्मिलित हैं, इसके लिए 0 [[सार्वभौमिक शीर्ष]] को प्रदर्शित करता है, और शून्य विभाजक को उन शीर्षों के रूप में पहचाना जा सकता है, जिनका 0 के अतिरिक्त कोई समीपस्थ बिन्दु है। क्योंकि इसमें सार्वभौमिक शीर्ष है, सभी वलय तत्वों का ग्राफ़ सदैव संयोजित रहता है और इसका व्यास अधिकतम दो तक रहता है। सभी शून्य विभाजकों का ग्राफ प्रत्येक वलय के लिए गैर-रिक्त है जो अभिन्न डोमेन नहीं है। यह इसी प्रकार संयोजित रहता है, इसका व्यास अधिकतम तीन रहता है,{{r|al}} और यदि इसमें चक्र उपस्थित रहते है तो इसका अधिकतम मान चार पर [[परिधि (ग्राफ़ सिद्धांत)]] द्वारा प्राप्त किया जाता है।{{r|mulay|ds}}
क्योंकि इसमें सार्वभौमिक शीर्ष है, सभी रिंग तत्वों का ग्राफ़ हमेशा जुड़ा रहता है और इसका व्यास अधिकतम दो होता है। सभी शून्य विभाजकों का ग्राफ प्रत्येक रिंग के लिए गैर-रिक्त है जो अभिन्न डोमेन नहीं है। यह जुड़ा रहता है, इसका व्यास अधिकतम तीन है,{{r|al}} और (यदि इसमें चक्र है) अधिकतम चार पर [[परिधि (ग्राफ़ सिद्धांत)]] है।{{r|mulay|ds}}
 
किसी वलय का शून्य-भाजक ग्राफ जो अभिन्न डोमेन नहीं है, वह परिमित मान को प्रदर्शित करने में सहयोगी रहता है, इसका कारण यह हैं क्योंकि वलय पूर्ण रूप से परिमित है।{{r|al}} इस प्रकार अधिक ठोस रूप से, यदि ग्राफ़ में अधिकतम डिग्री <math>d</math> है, तब इस स्थिति में इस वलय की अधिक से अधिक <math>(d^2-2d+2)^2</math> तत्व प्राप्त होते हैं।


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


{{harvtxt|Beck|1988}} अनुमान लगाया गया कि (पूर्ण ग्राफ़ की तरह) शून्य-भाजक ग्राफ़ में हमेशा समान क्लिक संख्या और [[रंगीन संख्या]] होती है। वैसे यह सत्य नहीं है; द्वारा प्रतिउदाहरण की खोज की गई थी {{harvtxt|Anderson|Naseer|1993}}.{{r|an}}
{{harvtxt|बेक|1988}} ने अनुमान लगाया गया कि पूर्ण ग्राफ़ के समान शून्य-भाजक ग्राफ़ में सदैव समान क्लिक संख्या और [[रंगीन संख्या]] होती है। वैसे यह सत्य नहीं है, क्योंकि इसके द्वारा प्रति-उदाहरण की खोज {{harvtxt|एंडर्सन|नसीर|1993}} द्वारा की गई थी।{{r|an}}


==संदर्भ==
==संदर्भ==

Revision as of 13:33, 23 July 2023

शून्य-भाजक ग्राफ , एकमात्र संभावित शून्य-भाजक ग्राफ जो पेड़ है लेकिन तारा नहीं है

गणित और विशेष रूप से संयोजक क्रमविनिमेय बीजगणित में शून्य-भाजक ग्राफ ऐसा अप्रत्यक्ष ग्राफ है, जो क्रमविनिमेय वलय के शून्य भाजक से प्राप्त होने वाले विभिन्न मानों का प्रतिनिधित्व करता है। इसमें वलय के विभिन्न तत्वों को इसके ग्राफ़ सिद्धांत के अनुसार प्राप्त होने वाले शीर्ष मानों के रूप में उपयोग किया जाता हैं, और इसके पश्चात इन तत्वों के संयुग्मों को जिनका उत्पाद शून्य से किया जाता है, इसके विभिन्न किनारों पर ग्राफ़ सिद्धांत का उपयोग करके इसके मौलिक रूप में प्रयुक्त होता हैं।[1]

परिभाषा

सामान्यतः उपयोग किए जाने वाले इस प्रकार के शून्य-भाजक ग्राफ के मूलतः दो रूप होते हैं। जिसमें इसकी मूल परिभाषा में बेक (1988) के नियम द्वारा इसके शीर्ष वलय के सभी तत्वों का प्रतिनिधित्व किया जाता हैं।[2] इसके पश्चात इसके संस्करण में अध्ययन किये जाने वाले एंडर्सन & लिविंगस्टन (1999), के द्वारा इसके शीर्ष पर दिए गए वलय के केवल शून्य विभाजक का प्रतिनिधित्व किया जाता हैं।[3]

उदाहरण

इस प्रकार यदि [[अर्ध अभाज्य संख्या]] है, जो दो अभाज्य संख्याओं के गुणनफल के समान हैं, तो इस प्रकार पुनः प्राप्त होने वाले विभिन्न पूर्णांकों के प्रारूपों के लिए इस वलय के शून्य-भाजक ग्राफ के शीर्षों के रूप में केवल शून्य भाजक के साथ या फिर पूर्णतः इस ग्राफ़ या पूर्ण द्विदलीय ग्राफ का उपयोग किया जाता है।

यह संपूर्ण ग्राफ़ है, इस स्थिति में होने पर कुछ अभाज्य संख्याओं के लिए को इस स्थिति में इसके शीर्ष पर प्राप्त होने वाले सभी शून्येतर गुणज के रूप में उपयोग किया जाता हैं, और इनमें से किन्हीं दो संख्याओं का गुणनफल 0 इस प्रारूप के लिए द्वारा प्रदर्शित किया जाता है।[3]

यह पूर्ण द्विदलीय ग्राफ है, इस स्थिति में को दो अलग-अलग अभाज्य संख्याओं के लिए और द्वारा विभाजित किया जाता हैं। इस प्रकार द्वि-विभाजन के दो पक्ष हैं, जहां पर के शून्येतर गुणज और यह के शून्येतर गुणज है। जो इन दोनो संख्याओं को जो स्वयं शून्य का प्रारूप नहीं हैं, इसलिए शून्य प्रारूप से गुणा करने पर यदि इसका गुणज प्राप्त होता है, और दूसरा का गुणज प्राप्त होता है, इस कारण इस ग्राफ़ में द्विविभाजन के विपरीत पक्षों पर शीर्षों के प्रत्येक संयोजन के बीच के किनारे का रूप प्रदर्शित होता है, और इस प्रकार इसका कोई अन्य किनारा नहीं है। इस कारण अधिकांशतः सामान्य रूप से शून्य-भाजक ग्राफ किसी भी वलय के लिए पूर्ण द्विदलीय ग्राफ है, जो दो अभिन्न डोमेन के विभिन्न उत्पादों का वलय है।[3]

एकमात्र चक्र ग्राफ जिन्हें शून्य-उत्पाद ग्राफ़ अर्ताथ शीर्ष के रूप में शून्य विभाजक के साथ इसके विभिन्न रूपों में देखा जा सकता है, जिसकी लंबाई 3 या 4 चक्रों के समान हैं।[3]

एकमात्र ट्री ग्राफ़ सिद्धांत जिसे शून्य-विभाजक ग्राफ़ के रूप में देखा जा सकता है, वह है स्टार ग्राफ़ सिद्धांत, जो पूर्ण रूप से द्विदलीय ग्राफ़ के रूप में प्रदर्शित होता हैं जो ट्री ग़्राफ सिद्धांत का स्वरूप हैं, और शून्य-भाजक ग्राफ़ के रूप में गठित पांच-शीर्ष ट्री हैं।[1][3]

गुण

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

किसी वलय का शून्य-भाजक ग्राफ जो अभिन्न डोमेन नहीं है, वह परिमित मान को प्रदर्शित करने में सहयोगी रहता है, इसका कारण यह हैं क्योंकि वलय पूर्ण रूप से परिमित है।[3] इस प्रकार अधिक ठोस रूप से, यदि ग्राफ़ में अधिकतम डिग्री है, तब इस स्थिति में इस वलय की अधिक से अधिक तत्व प्राप्त होते हैं।

यदि वलय और ग्राफ के अनंत मान होते हैं, तो प्रत्येक किनारे का समापन बिंदु होता है, जिसमें अनंत रूप से कई समीपस्थ बिंदु होते हैं।[1]

बेक (1988) ने अनुमान लगाया गया कि पूर्ण ग्राफ़ के समान शून्य-भाजक ग्राफ़ में सदैव समान क्लिक संख्या और रंगीन संख्या होती है। वैसे यह सत्य नहीं है, क्योंकि इसके द्वारा प्रति-उदाहरण की खोज एंडर्सन & नसीर (1993) द्वारा की गई थी।[6]

संदर्भ

  1. 1.0 1.1 1.2 Anderson, David F.; Axtell, Michael C.; Stickles, Joe A., Jr. (2011), "Zero-divisor graphs in commutative rings", Commutative algebra—Noetherian and non-Noetherian perspectives, Springer, New York, pp. 23–45, doi:10.1007/978-1-4419-6990-3_2, MR 2762487{{citation}}: CS1 maint: multiple names: authors list (link)
  2. Beck, István (1988), "Coloring of commutative rings", Journal of Algebra, 116 (1): 208–226, doi:10.1016/0021-8693(88)90202-5, MR 0944156
  3. 3.0 3.1 3.2 3.3 3.4 3.5 3.6 Anderson, David F.; Livingston, Philip S. (1999), "The zero-divisor graph of a commutative ring", Journal of Algebra, 217 (2): 434–447, doi:10.1006/jabr.1998.7840, MR 1700509
  4. Mulay, S. B. (2002), "Cycles and symmetries of zero-divisors", Communications in Algebra, 30 (7): 3533–3558, doi:10.1081/AGB-120004502, MR 1915011
  5. DeMeyer, Frank; Schneider, Kim (2002), "Automorphisms and zero divisor graphs of commutative rings", Commutative rings, Hauppauge, NY: Nova Science, pp. 25–37, MR 2037656
  6. Anderson, D. D.; Naseer, M. (1993), "Beck's coloring of a commutative ring", Journal of Algebra, 159 (2): 500–514, doi:10.1006/jabr.1993.1171, MR 1231228