सर्कुलेंट ग्राफ: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Undirected graph acted on by a vertex-transitive cyclic group of symmetries}}
{{short description|Undirected graph acted on by a vertex-transitive cyclic group of symmetries}}
{{For|the square matrices|Circulant matrix}}
{{For|स्क्वायर मेट्रिसेस|सर्कुलेंट मैट्रिक्स}}


[[File:Paley13.svg|thumb|240px|ऑर्डर 13 का [[पाले ग्राफ]] सर्कुलेंट ग्राफ का उदाहरण है।]][[ ग्राफ सिद्धांत |ग्राफ सिद्धांत]] में, सर्कुलेंट ग्राफ [[अप्रत्यक्ष ग्राफ]] है, जो [[ग्राफ ऑटोमोर्फिज्म|समरूपता]] के [[चक्रीय समूह]] द्वारा क्रियान्वित, [[शीर्ष-सकर्मक ग्राफ]] होता है। इसे कभी-कभी चक्रीय ग्राफ कहा जाता है,<ref name="ds1"/>किन्तु इस शब्द के अन्य अर्थ भी होते हैं।
[[File:Paley13.svg|thumb|240px|ऑर्डर 13 का [[पाले ग्राफ]] सर्कुलेंट ग्राफ का उदाहरण है।]][[ ग्राफ सिद्धांत |ग्राफ सिद्धांत]] में, सर्कुलेंट ग्राफ [[अप्रत्यक्ष ग्राफ]] है, जो [[ग्राफ ऑटोमोर्फिज्म|समरूपता]] के [[चक्रीय समूह]] द्वारा क्रियान्वित, [[शीर्ष-सकर्मक ग्राफ]] होता है। इसे कभी-कभी चक्रीय ग्राफ कहा जाता है,<ref name="ds1"/>किन्तु इस शब्द के अन्य अर्थ भी होते हैं।
Line 27: Line 27:
प्रत्येक [[चक्र ग्राफ]] सर्कुलेंट ग्राफ है, जैसा कि प्रत्येक [[क्राउन ग्राफ]] में 2 मॉडुलो 4 शीर्ष होते हैं।  
प्रत्येक [[चक्र ग्राफ]] सर्कुलेंट ग्राफ है, जैसा कि प्रत्येक [[क्राउन ग्राफ]] में 2 मॉडुलो 4 शीर्ष होते हैं।  


क्रम {{mvar|n}} का पाले ग्राफ़ (जहाँ {{mvar|n}}, 1 मॉड्यूल 4 के अनुरूप [[अभाज्य संख्या]] है) जिसमें शीर्ष की संख्याएँ 0 से {{math|''n'' &minus; 1}} तक होती हैं और दो शीर्ष आसन्न हैं, यदि उनका अंतर [[द्विघात अवशेष]] मॉड्यूलो {{mvar|n}} होता है। चूँकि कोर की उपस्थिति या अनुपस्थिति मात्र दो शीर्ष संख्याओं के अंतर मॉड्यूल {{mvar|n}} पर निर्भर करती है, कोई भी पाले ग्राफ सर्कुलेंट ग्राफ होता है।
क्रम {{mvar|n}} का पाले ग्राफ़ (जहाँ {{mvar|n}}, 1 मॉड्यूल 4 के अनुरूप [[अभाज्य संख्या]] है) जिसमें शीर्ष की संख्याएँ 0 से {{math|''n'' &minus; 1}} तक होती हैं और दो शीर्ष आसन्न होंगे, यदि उनका अंतर [[द्विघात अवशेष]] मॉड्यूलो {{mvar|n}} होता है। चूँकि कोर की उपस्थिति या अनुपस्थिति मात्र दो शीर्ष संख्याओं के अंतर मॉड्यूल {{mvar|n}} पर निर्भर करती है, कोई भी पाले ग्राफ सर्कुलेंट ग्राफ होता है।


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


अगर दो नंबर {{mvar|m}} और {{mvar|n}} अपेक्षाकृत प्रमुख हैं, तो {{math|''m'' &times; ''n''}} रूक का ग्राफ़ (एक ग्राफ़ जिसमें प्रत्येक वर्ग के लिए एक वर्टेक्स होता है {{math|''m'' &times; ''n''}} शतरंज की बिसात और प्रत्येक दो वर्गों के लिए एक किनारा जिसे एक शतरंज का बदमाश एक ही चाल में चला सकता है) एक गोलाकार ग्राफ है। ऐसा इसलिए है क्योंकि इसकी समरूपता में उपसमूह के रूप में चक्रीय समूह सी सम्मिलित है<sub>mn</sub> <math>\simeq</math>सी<sub>m</sub>×C<sub>n</sub>. अधिक आम तौर पर, इस मामले में, किसी के बीच ग्राफ का टेन्सर उत्पाद {{mvar|m}}- और {{mvar|n}}-वर्टेक्स सर्कुलेंट्स अपने आप में एक सर्कुलेंट है।<ref name="v04"/>
यदि दो संख्याएँ {{mvar|m}} और {{mvar|n}} अपेक्षाकृत प्रमुख हैं, तो {{math|''m'' &times; ''n''}} रूक का ग्राफ़ (ग्राफ़ जिसमें {{math|''m'' &times; ''n''}} शतरंजबोर्ड के प्रत्येक वर्ग के लिए शीर्ष है और प्रत्येक दो वर्गों के लिए कोर है जो शतरंज के रूक के मध्य समान चलन में आगे बढ़ सकता है) सर्कुलेंट ग्राफ है। ऐसा इसलिए है क्योंकि इसकी समरूपता में उपसमूह के रूप में चक्रीय समूह ''C<sub>mn</sub> C<sub>m</sub>''×''C<sub>n</sub>'' सम्मिलित है। सामान्यतः, इस स्थिति में, किसी भी {{mvar|m}}- और {{mvar|n}}-शीर्ष सर्कुलेंट के मध्य ग्राफ का टेन्सर गुणनफल स्वयं सर्कुलेंट होता है।<ref name="v04"/>


[[रैमसे संख्या]] पर ज्ञात निचली सीमाओं में से कई सर्कुलेंट ग्राफ़ के उदाहरणों से आते हैं जिनमें छोटे अधिकतम क्लिक्स और छोटे [[अधिकतम स्वतंत्र सेट]] होते हैं।<ref name="ds1">[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1 Small Ramsey Numbers], Stanisław P. Radziszowski, ''[[Electronic Journal of Combinatorics|Electronic J. Combinatorics]]'', dynamic survey&nbsp;1, updated 2014.</ref>
[[रैमसे संख्या]] पर ज्ञात निचली सीमाओं में से कई सर्कुलेंट ग्राफ़ के उदाहरणों से आते हैं जिनमें छोटे अधिकतम क्लिक्स और छोटे [[अधिकतम स्वतंत्र सेट]] होते हैं।<ref name="ds1">[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1 Small Ramsey Numbers], Stanisław P. Radziszowski, ''[[Electronic Journal of Combinatorics|Electronic J. Combinatorics]]'', dynamic survey&nbsp;1, updated 2014.</ref>
Line 61: Line 61:
होने देना {{mvar|a}} एक पूर्णांक हो जो अपेक्षाकृत प्रमुख हो {{mvar|n}}, और जाने {{mvar|b}} कोई पूर्णांक हो। फिर रैखिक कार्य जो एक संख्या लेता है {{mvar|x}} को {{math|''ax'' + ''b''}} एक सर्कुलेंट नंबरिंग को दूसरे सर्कुलेंट नंबरिंग में बदल देता है। एंड्रस एडम ने अनुमान लगाया कि ये रेखीय मानचित्र सर्कुलेंट संपत्ति को संरक्षित करते हुए सर्कुलेंट ग्राफ को फिर से क्रमांकित करने के एकमात्र तरीके हैं: अर्थात, यदि {{mvar|G}} और {{mvar|H}} आइसोमॉर्फिक सर्कुलेंट ग्राफ़ हैं, अलग-अलग नंबरिंग के साथ, फिर एक लीनियर मैप है जो नंबरिंग को बदल देता है {{mvar|G}} के लिए नंबरिंग में {{mvar|H}}. हालाँकि, एडम का अनुमान अब झूठा माना जाता है। रेखांकन द्वारा एक प्रति उदाहरण दिया गया है {{mvar|G}} और {{mvar|H}} प्रत्येक 16 शीर्षों के साथ; एक शिखर {{mvar|x}} में {{mvar|G}} छह पड़ोसियों से जुड़ा है {{math|''x'' ± 1}}, {{math|''x'' ± 2}}, और {{math|''x'' ± 7}} मॉड्यूल 16, जबकि अंदर {{mvar|H}} छह पड़ोसी हैं {{math|''x'' ± 2}}, {{math|''x'' ± 3}}, और {{math|''x'' ± 5}} मोडुलो 16। ये दो रेखांकन समरूपी हैं, किन्तु उनके समरूपता को एक रेखीय मानचित्र द्वारा महसूस नहीं किया जा सकता है।<ref name="v04"/>
होने देना {{mvar|a}} एक पूर्णांक हो जो अपेक्षाकृत प्रमुख हो {{mvar|n}}, और जाने {{mvar|b}} कोई पूर्णांक हो। फिर रैखिक कार्य जो एक संख्या लेता है {{mvar|x}} को {{math|''ax'' + ''b''}} एक सर्कुलेंट नंबरिंग को दूसरे सर्कुलेंट नंबरिंग में बदल देता है। एंड्रस एडम ने अनुमान लगाया कि ये रेखीय मानचित्र सर्कुलेंट संपत्ति को संरक्षित करते हुए सर्कुलेंट ग्राफ को फिर से क्रमांकित करने के एकमात्र तरीके हैं: अर्थात, यदि {{mvar|G}} और {{mvar|H}} आइसोमॉर्फिक सर्कुलेंट ग्राफ़ हैं, अलग-अलग नंबरिंग के साथ, फिर एक लीनियर मैप है जो नंबरिंग को बदल देता है {{mvar|G}} के लिए नंबरिंग में {{mvar|H}}. हालाँकि, एडम का अनुमान अब झूठा माना जाता है। रेखांकन द्वारा एक प्रति उदाहरण दिया गया है {{mvar|G}} और {{mvar|H}} प्रत्येक 16 शीर्षों के साथ; एक शिखर {{mvar|x}} में {{mvar|G}} छह पड़ोसियों से जुड़ा है {{math|''x'' ± 1}}, {{math|''x'' ± 2}}, और {{math|''x'' ± 7}} मॉड्यूल 16, जबकि अंदर {{mvar|H}} छह पड़ोसी हैं {{math|''x'' ± 2}}, {{math|''x'' ± 3}}, और {{math|''x'' ± 5}} मोडुलो 16। ये दो रेखांकन समरूपी हैं, किन्तु उनके समरूपता को एक रेखीय मानचित्र द्वारा महसूस नहीं किया जा सकता है।<ref name="v04"/>


टायडा का अनुमान केवल सर्कुलेंट ग्राफ के एक विशेष वर्ग पर विचार करके एडम के अनुमान को परिष्कृत करता है, जिसमें आसन्न ग्राफ वर्टिकल के बीच के सभी अंतर वर्टिकल की संख्या के अपेक्षाकृत प्रमुख हैं। इस परिष्कृत अनुमान के अनुसार, इन विशेष सर्कुलेंट ग्राफ़ में यह गुण होना चाहिए कि उनकी सभी समरूपताएँ संख्याओं के अंतर्निहित योगात्मक समूह की समरूपता से आती हैं। {{math|''n''}}. यह 2001 और 2002 में दो समूहों द्वारा सिद्ध किया गया था।<ref>{{citation
टायडा का अनुमान केवल सर्कुलेंट ग्राफ के एक विशेष वर्ग पर विचार करके एडम के अनुमान को परिष्कृत करता है, जिसमें आसन्न ग्राफ वर्टिकल के मध्य के सभी अंतर वर्टिकल की संख्या के अपेक्षाकृत प्रमुख हैं। इस परिष्कृत अनुमान के अनुसार, इन विशेष सर्कुलेंट ग्राफ़ में यह गुण होना चाहिए कि उनकी सभी समरूपताएँ संख्याओं के अंतर्निहित योगात्मक समूह की समरूपता से आती हैं। {{math|''n''}}. यह 2001 और 2002 में दो समूहों द्वारा सिद्ध किया गया था।<ref>{{citation
  | last1 = Muzychuk | first1 = Mikhail
  | last1 = Muzychuk | first1 = Mikhail
  | last2 = Klin | first2 = Mikhail
  | last2 = Klin | first2 = Mikhail

Revision as of 16:01, 2 May 2023

ऑर्डर 13 का पाले ग्राफ सर्कुलेंट ग्राफ का उदाहरण है।

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

समतुल्य परिभाषाएँ

सर्कुलेंट ग्राफ़ का वर्णन विभिन्न समान प्रकारों से किया जा सकता है-[2]

  • ग्राफ़ के ऑटोमॉर्फिज़्म समूह में चक्रीय उपसमूह सम्मिलित होता है जो ग्राफ़ के शीर्ष पर समूह क्रिया (गणित) करता है। अन्य शब्दों में, ग्राफ़ में ऑटोमोर्फिज्म समूह होता है, जो इसके शीर्षों का चक्रीय क्रमचय है।
  • ग्राफ़ में आसन्न मैट्रिक्स होता है जो सर्कुलेंट मैट्रिक्स है।
  • ग्राफ़ के n शीर्षों को 0 से लेकर n − 1 तक इस प्रकार क्रमांकित किया जा सकता है कि, यदि दो शीर्ष x और (x + d) mod n आसन्न हैं, तो प्रत्येक दो शीर्षों z और (z + d) mod n को क्रमांकित किया जाता है। मॉड n आसन्न होते हैं।
  • ग्राफ़ निर्मित किया जा सकता है (संभवतः क्रॉसिंग के साथ) जिसमें इसके शीर्ष नियमित बहुभुज के शीर्षों पर स्थित होते हैं और बहुभुज की प्रत्येक घूर्णी समरूपता भी आरेखण की समरूपता होती है।
  • ग्राफ, चक्रीय समूह का केली ग्राफ है।[3]


उदाहरण

प्रत्येक चक्र ग्राफ सर्कुलेंट ग्राफ है, जैसा कि प्रत्येक क्राउन ग्राफ में 2 मॉडुलो 4 शीर्ष होते हैं।

क्रम n का पाले ग्राफ़ (जहाँ n, 1 मॉड्यूल 4 के अनुरूप अभाज्य संख्या है) जिसमें शीर्ष की संख्याएँ 0 से n − 1 तक होती हैं और दो शीर्ष आसन्न होंगे, यदि उनका अंतर द्विघात अवशेष मॉड्यूलो n होता है। चूँकि कोर की उपस्थिति या अनुपस्थिति मात्र दो शीर्ष संख्याओं के अंतर मॉड्यूल n पर निर्भर करती है, कोई भी पाले ग्राफ सर्कुलेंट ग्राफ होता है।

प्रत्येक मोबियस सीढ़ी सर्कुलेंट ग्राफ है, जैसा कि प्रत्येक पूर्ण ग्राफ होता है। पूर्ण द्विदलीय ग्राफ सर्कुलेंट ग्राफ है यदि इसके द्विभाजन के दोनों ओर समान संख्या में शीर्ष हैं।

यदि दो संख्याएँ m और n अपेक्षाकृत प्रमुख हैं, तो m × n रूक का ग्राफ़ (ग्राफ़ जिसमें m × n शतरंजबोर्ड के प्रत्येक वर्ग के लिए शीर्ष है और प्रत्येक दो वर्गों के लिए कोर है जो शतरंज के रूक के मध्य समान चलन में आगे बढ़ सकता है) सर्कुलेंट ग्राफ है। ऐसा इसलिए है क्योंकि इसकी समरूपता में उपसमूह के रूप में चक्रीय समूह Cmn Cm×Cn सम्मिलित है। सामान्यतः, इस स्थिति में, किसी भी m- और n-शीर्ष सर्कुलेंट के मध्य ग्राफ का टेन्सर गुणनफल स्वयं सर्कुलेंट होता है।[2]

रैमसे संख्या पर ज्ञात निचली सीमाओं में से कई सर्कुलेंट ग्राफ़ के उदाहरणों से आते हैं जिनमें छोटे अधिकतम क्लिक्स और छोटे अधिकतम स्वतंत्र सेट होते हैं।[1]


एक विशिष्ट उदाहरण

गोलाकार ग्राफ छलांग के साथ के साथ ग्राफ के रूप में परिभाषित किया गया है नोड्स लेबल जहां प्रत्येक नोड i 2k नोड्स के निकट है .

  • लेखाचित्र अगर और केवल अगर जुड़ा हुआ है .
  • अगर निश्चित पूर्णांक हैं तो फैले हुए पेड़ों की संख्या कहाँ आदेश के पुनरावृत्ति संबंध को संतुष्ट करता है .

स्व पूरक परिसंचारी

एक स्व-पूरक ग्राफ एक ऐसा ग्राफ है जिसमें प्रत्येक किनारे को एक गैर-किनारे द्वारा प्रतिस्थापित किया जाता है और इसके विपरीत एक ग्राफ समरूपता ग्राफ बनाता है। उदाहरण के लिए, एक पांच-शीर्ष चक्र ग्राफ स्व-पूरक है, और एक सर्कुलेंट ग्राफ भी है। आम तौर पर प्राइम ऑर्डर का हर पाले ग्राफ एक स्व-पूरक सर्कुलेंट ग्राफ होता है।[4] होर्स्ट सैक्स ने दिखाया कि यदि एक संख्या n के पास वह गुण है जिसका प्रत्येक अभाज्य गुणनखंड n के अनुरूप है 1 modulo 4, तो इसके साथ एक स्व-पूरक परिसंचारक मौजूद है n शिखर। उन्होंने अनुमान लगाया कि यह शर्त भी आवश्यक है: कि कोई अन्य मूल्य नहीं n स्व-पूरक परिसंचारक के अस्तित्व की अनुमति दें।[2][4]विलफ्रेड द्वारा लगभग 40 साल बाद अनुमान सिद्ध किया गया था।[2]


Ádám का अनुमान

एक सर्कुलेंट ग्राफ की सर्कुलेंट नंबरिंग को 0 से लेकर संख्याओं द्वारा ग्राफ के कोने की लेबलिंग के रूप में परिभाषित करें n − 1 इस तरह से कि, यदि कुछ दो शीर्षों को क्रमांकित किया गया है x और y सन्निकट हैं, तो प्रत्येक दो शीर्षों को क्रमांकित किया गया है z और (zx + y) mod n सटे हुए हैं। समतुल्य रूप से, एक सर्कुलेंट नंबरिंग वर्टिकल की एक संख्या है जिसके लिए ग्राफ का आसन्न मैट्रिक्स एक सर्कुलेंट मैट्रिक्स है।

होने देना a एक पूर्णांक हो जो अपेक्षाकृत प्रमुख हो n, और जाने b कोई पूर्णांक हो। फिर रैखिक कार्य जो एक संख्या लेता है x को ax + b एक सर्कुलेंट नंबरिंग को दूसरे सर्कुलेंट नंबरिंग में बदल देता है। एंड्रस एडम ने अनुमान लगाया कि ये रेखीय मानचित्र सर्कुलेंट संपत्ति को संरक्षित करते हुए सर्कुलेंट ग्राफ को फिर से क्रमांकित करने के एकमात्र तरीके हैं: अर्थात, यदि G और H आइसोमॉर्फिक सर्कुलेंट ग्राफ़ हैं, अलग-अलग नंबरिंग के साथ, फिर एक लीनियर मैप है जो नंबरिंग को बदल देता है G के लिए नंबरिंग में H. हालाँकि, एडम का अनुमान अब झूठा माना जाता है। रेखांकन द्वारा एक प्रति उदाहरण दिया गया है G और H प्रत्येक 16 शीर्षों के साथ; एक शिखर x में G छह पड़ोसियों से जुड़ा है x ± 1, x ± 2, और x ± 7 मॉड्यूल 16, जबकि अंदर H छह पड़ोसी हैं x ± 2, x ± 3, और x ± 5 मोडुलो 16। ये दो रेखांकन समरूपी हैं, किन्तु उनके समरूपता को एक रेखीय मानचित्र द्वारा महसूस नहीं किया जा सकता है।[2]

टायडा का अनुमान केवल सर्कुलेंट ग्राफ के एक विशेष वर्ग पर विचार करके एडम के अनुमान को परिष्कृत करता है, जिसमें आसन्न ग्राफ वर्टिकल के मध्य के सभी अंतर वर्टिकल की संख्या के अपेक्षाकृत प्रमुख हैं। इस परिष्कृत अनुमान के अनुसार, इन विशेष सर्कुलेंट ग्राफ़ में यह गुण होना चाहिए कि उनकी सभी समरूपताएँ संख्याओं के अंतर्निहित योगात्मक समूह की समरूपता से आती हैं। n. यह 2001 और 2002 में दो समूहों द्वारा सिद्ध किया गया था।[5][6]


एल्गोरिथम प्रश्न

सर्कुलेंट ग्राफ़ के लिए एक बहुपद-समय मान्यता एल्गोरिथ्म है, और सर्कुलेंट ग्राफ़ के लिए आइसोमोर्फिज़्म समस्या को बहुपद समय में हल किया जा सकता है।[7][8]


संदर्भ

  1. 1.0 1.1 Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey 1, updated 2014.
  2. 2.0 2.1 2.2 2.3 2.4 Vilfred, V. (2004), "On circulant graphs", in Balakrishnan, R.; Sethuraman, G.; Wilson, Robin J. (eds.), Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001), Alpha Science, pp. 34–36.
  3. Alspach, Brian (1997), "Isomorphism and Cayley graphs on abelian groups", Graph symmetry (Montreal, PQ, 1996), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 497, Dordrecht: Kluwer Acad. Publ., pp. 1–22, MR 1468786.
  4. 4.0 4.1 Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen. 9: 270–288. MR 0151953..
  5. Muzychuk, Mikhail; Klin, Mikhail; Pöschel, Reinhard (2001), "The isomorphism problem for circulant graphs via Schur ring theory", Codes and association schemes (Piscataway, NJ, 1999), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 56, Providence, Rhode Island: American Mathematical Society, pp. 241–264, MR 1816402
  6. Dobson, Edward; Morris, Joy (2002), "Toida's conjecture is true", Electronic Journal of Combinatorics, 9 (1): R35:1–R35:14, MR 1928787
  7. Muzychuk, Mikhail (2004). "A Solution of the Isomorphism Problem for Circulant Graphs". Proc. London Math. Soc. 88: 1–41. doi:10.1112/s0024611503014412. MR 2018956.
  8. Evdokimov, Sergei; Ponomarenko, Ilia (2004). "Recognition and verification of an isomorphism of circulant graphs in polynomial time". St. Petersburg Math. J. 15: 813–835. doi:10.1090/s1061-0022-04-00833-7. MR 2044629.


बाहरी संबंध