सर्कुलेंट ग्राफ: Difference between revisions
No edit summary |
No edit summary |
||
| Line 33: | Line 33: | ||
यदि दो संख्याएँ {{mvar|m}} और {{mvar|n}} अपेक्षाकृत प्रमुख हैं, तो {{math|''m'' × ''n''}} रूक का ग्राफ़ (ग्राफ़ जिसमें {{math|''m'' × ''n''}} शतरंजबोर्ड के प्रत्येक वर्ग के लिए शीर्ष है और प्रत्येक दो वर्गों के लिए कोर है जो शतरंज के रूक के मध्य समान चलन में आगे बढ़ सकता है) सर्कुलेंट ग्राफ है। ऐसा इसलिए है क्योंकि इसकी समरूपता में उपसमूह के रूप में चक्रीय समूह ''C<sub>mn</sub> C<sub>m</sub>''×''C<sub>n</sub>'' सम्मिलित है। सामान्यतः, इस स्थिति में, किसी भी {{mvar|m}}- और {{mvar|n}}-शीर्ष सर्कुलेंट के मध्य ग्राफ का टेन्सर गुणनफल स्वयं सर्कुलेंट होता है।<ref name="v04"/> | यदि दो संख्याएँ {{mvar|m}} और {{mvar|n}} अपेक्षाकृत प्रमुख हैं, तो {{math|''m'' × ''n''}} रूक का ग्राफ़ (ग्राफ़ जिसमें {{math|''m'' × ''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 1, updated 2014.</ref> | ||
== | == विशिष्ट उदाहरण == | ||
<math> s_1, \ldots, s_k </math> के साथ सर्कुलेंट ग्राफ <math> C_n^{s_1,\ldots,s_k} </math> को <math>0, 1, \ldots, n-1</math> लेबल वाले <math> n </math> नोड्स के ग्राफ के रूप में परिभाषित किया गया है जहाँ प्रत्येक नोड i 2k नोड्स <math>i \pm s_1, \ldots, i \pm s_k \mod n</math> के निकट है। | |||
* | * ग्राफ <math>C_n^{s_1, \ldots, s_k}</math> जुड़ा हुआ है, यदि <math>\gcd(n, s_1, \ldots, s_k) = 1</math> है। | ||
* | * यदि <math> 1 \leq s_1 < \cdots < s_k </math> निश्चित पूर्णांक हैं तो स्पैनिन्ग ट्रीज की संख्या <math>t(C_n^{s_1,\ldots,s_k})=na_n^2</math> होगी, जहाँ <math>a_n</math> ऑर्डर <math>2^{s_k-1}</math> के [[पुनरावृत्ति संबंध]] को संतुष्ट करता है। | ||
** विशेष रूप से, <math>t(C_n^{1,2}) = nF_n^2 </math> | ** विशेष रूप से, <math>t(C_n^{1,2}) = nF_n^2 </math> जहाँ <math>F_n</math> n-वें [[फाइबोनैचि संख्या]] है। | ||
==स्व पूरक परिसंचारी== | ==स्व पूरक परिसंचारी== | ||
[[स्व-पूरक ग्राफ]] ऐसा ग्राफ है जिसमें प्रत्येक कोर को गैर-कोर द्वारा प्रतिस्थापित किया जाता है और इसके विपरीत [[ ग्राफ समरूपता | ग्राफ समरूपता]] का उत्पादन होता है। | |||
उदाहरण के लिए, | |||
उदाहरण के लिए, पांच-शीर्ष चक्र ग्राफ, स्व-पूरक और सर्कुलेंट ग्राफ भी है। सामान्यतः प्राइम ऑर्डर का प्रत्येक पाले ग्राफ स्व-पूरक सर्कुलेंट ग्राफ होता है।<ref name="s62">{{Cite journal | |||
| last = Sachs | first = Horst | authorlink = Horst Sachs | | last = Sachs | first = Horst | authorlink = Horst Sachs | ||
| mr = 0151953 | | mr = 0151953 | ||
| Line 53: | Line 54: | ||
| title = Über selbstkomplementäre Graphen | | title = Über selbstkomplementäre Graphen | ||
| volume = 9 | | volume = 9 | ||
| year = 1962}}.</ref> [[होर्स्ट सैक्स]] ने | | year = 1962}}.</ref> [[होर्स्ट सैक्स]] ने प्रदर्शित किया कि यदि संख्या {{mvar|n}} में यह गुण है कि {{mvar|n}} का प्रत्येक अभाज्य गुणनखंड 1 मॉड्यूल 4 के सर्वांगसम है, तो {{mvar|n}} शीर्षों के साथ स्व-पूरक परिसंचारक उपस्थित है। उन्होंने अनुमान लगाया कि यह स्तिथि भी आवश्यक है, कि {{mvar|n}} का कोई अन्य मान स्व-पूरक परिसंचारक के अस्तित्व की अनुमति नहीं देता है।<ref name="v04" /><ref name="s62" />विलफ्रेड द्वारा प्रायः 40 वर्ष पश्चात यह अनुमान सिद्ध किया गया था।<ref name="v04" /> | ||
Revision as of 16:55, 2 May 2023
ग्राफ सिद्धांत में, सर्कुलेंट ग्राफ अप्रत्यक्ष ग्राफ है, जो समरूपता के चक्रीय समूह द्वारा क्रियान्वित, शीर्ष-सकर्मक ग्राफ होता है। इसे कभी-कभी चक्रीय ग्राफ कहा जाता है,[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 नोड्स के निकट है।
- ग्राफ जुड़ा हुआ है, यदि है।
- यदि निश्चित पूर्णांक हैं तो स्पैनिन्ग ट्रीज की संख्या होगी, जहाँ ऑर्डर के पुनरावृत्ति संबंध को संतुष्ट करता है।
- विशेष रूप से, जहाँ n-वें फाइबोनैचि संख्या है।
स्व पूरक परिसंचारी
स्व-पूरक ग्राफ ऐसा ग्राफ है जिसमें प्रत्येक कोर को गैर-कोर द्वारा प्रतिस्थापित किया जाता है और इसके विपरीत ग्राफ समरूपता का उत्पादन होता है।
उदाहरण के लिए, पांच-शीर्ष चक्र ग्राफ, स्व-पूरक और सर्कुलेंट ग्राफ भी है। सामान्यतः प्राइम ऑर्डर का प्रत्येक पाले ग्राफ स्व-पूरक सर्कुलेंट ग्राफ होता है।[4] होर्स्ट सैक्स ने प्रदर्शित किया कि यदि संख्या n में यह गुण है कि n का प्रत्येक अभाज्य गुणनखंड 1 मॉड्यूल 4 के सर्वांगसम है, तो n शीर्षों के साथ स्व-पूरक परिसंचारक उपस्थित है। उन्होंने अनुमान लगाया कि यह स्तिथि भी आवश्यक है, कि n का कोई अन्य मान स्व-पूरक परिसंचारक के अस्तित्व की अनुमति नहीं देता है।[2][4]विलफ्रेड द्वारा प्रायः 40 वर्ष पश्चात यह अनुमान सिद्ध किया गया था।[2]
Ádám का अनुमान
एक सर्कुलेंट ग्राफ की सर्कुलेंट नंबरिंग को 0 से लेकर संख्याओं द्वारा ग्राफ के कोने की लेबलिंग के रूप में परिभाषित करें n − 1 इस तरह से कि, यदि कुछ दो शीर्षों को क्रमांकित किया गया है x और y सन्निकट हैं, तो प्रत्येक दो शीर्षों को क्रमांकित किया गया है z और (z − x + 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.0 1.1 Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey 1, updated 2014.
- ↑ 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.
- ↑ 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.0 4.1 Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen. 9: 270–288. MR 0151953..
- ↑ 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
- ↑ Dobson, Edward; Morris, Joy (2002), "Toida's conjecture is true", Electronic Journal of Combinatorics, 9 (1): R35:1–R35:14, MR 1928787
- ↑ 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.
- ↑ 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.
