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

Latest revision as of 10:45, 4 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 \times n$ रूक का ग्राफ़ (ग्राफ़ जिसमें $m \times n$ शतरंजबोर्ड के प्रत्येक वर्ग के लिए शीर्ष है और प्रत्येक दो वर्गों के लिए कोर है जो शतरंज के रूक के मध्य समान चलन में आगे बढ़ सकता है) सर्कुलेंट ग्राफ है। ऐसा इसलिए है क्योंकि इसकी समरूपता में उपसमूह के रूप में चक्रीय समूह C_mn C_m×C_n सम्मिलित है। सामान्यतः, इस स्थिति में, $m$ - और $n$ -शीर्ष के मध्य ग्राफ का टेन्सर गुणनफल सर्कुलेंट होता है।^[2]

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

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

$s_{1},\ldots ,s_{k}$ के साथ सर्कुलेंट ग्राफ $C_{n}^{s_{1},\ldots ,s_{k}}$ को $0,1,\ldots ,n-1$ लेबल वाले $n$ शीर्षों के ग्राफ के रूप में परिभाषित किया गया है जहाँ प्रत्येक शीर्ष i, 2k शीर्षों $i\pm s_{1},\ldots ,i\pm s_{k}\mod n$ के निकट है।

यदि $\gcd(n,s_{1},\ldots ,s_{k})=1$ है, तो ग्राफ $C_{n}^{s_{1},\ldots ,s_{k}}$ युग्मित है।
यदि $1\leq s_{1}<\cdots <s_{k}$ $1\leq s_{1}<\cdots <s_{k}$ निश्चित पूर्णांक हैं तो स्पैनिन्ग ट्रीज की संख्या $t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}$ $t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}$ है, जहाँ $a_{n}$ $a_{n}$ ऑर्डर $2^{s_{k}-1}$ $2^{s_{k}-1}$ के पुनरावृत्ति संबंध को संतुष्ट करता है।
- विशेष रूप से, $t(C_{n}^{1,2})=nF_{n}^{2}$ जहाँ $F_{n}$ n-वीं फाइबोनैचि संख्या है।

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

स्व-पूरक ग्राफ के प्रत्येक कोर को गैर-कोर द्वारा प्रतिस्थापित किया जाता है और इसके विपरीत ग्राफ समरूपता का उत्पादन होता है।

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

एडम का अनुमान

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

मान लीजिए $a$ पूर्णांक है जो $n$ से सह-अभाज्य है, और $b$ कोई पूर्णांक है। तब, रैखिक फलन जो संख्या $x$ को $ax + b$ में ले जाता है, जो सर्कुलेंट नंबरिंग को अन्य सर्कुलेंट नंबरिंग में परिवर्तित कर देता है। एंड्रस एडम ने अनुमान लगाया कि ये रैखिक मानचित्र सर्कुलेंट गुण को संरक्षित करते हुए सर्कुलेंट ग्राफ को पुनः क्रमांकित करने का एकमात्र प्रकार है। अर्थात, यदि $G$ और $H$ भिन्न-भिन्न नंबरिंग के साथ आइसोमॉर्फिक सर्कुलेंट ग्राफ़ हैं, तो रैखिक मानचित्र $G$ की नंबरिंग को $H$ के लिए परिवर्तित कर देता है। चूँकि, एडम के अनुमान को वर्तमान में असत्य माना जाता है। ग्राफ $G$ और $H$ प्रत्येक 16 शीर्षों के साथ प्रति उदाहरण दिया गया है, जिसमें $G$ में शीर्ष $x$ छह प्रतिवेशियों $x \pm 1$ , $x \pm 2$ , और $x \pm 7$ मॉड्यूल 16 से युग्मित है, जबकि $H$ में छह प्रतिवेशी $x \pm 2$ , $x \pm 3$ , और $x \pm 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.

बाहरी संबंध

Weisstein, Eric W. "Circulant Graph". MathWorld.

[ds1-1] 1.0 ^1.1 Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey 1, updated 2014.

[v04-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.

[s62-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

[muz04-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.

[ep04-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
 {{short description|Undirected graph acted on by a vertex-transitive cyclic group of symmetries}}
-{{For|स्क्वायर मेट्रिसेस|सर्कुलेंट मैट्रिक्स}}
+{{For|स्क्वायर आव्यूह|सर्कुलेंट आव्यूह}}
-[[File:Paley13.svg|thumb|240px|ऑर्डर 13 का [[पाले ग्राफ]] सर्कुलेंट ग्राफ का उदाहरण है।]][[ ग्राफ सिद्धांत |ग्राफ सिद्धांत]] में, सर्कुलेंट ग्राफ [[अप्रत्यक्ष ग्राफ]] है, जो [[ग्राफ ऑटोमोर्फिज्म|समरूपता]] के [[चक्रीय समूह]] द्वारा क्रियान्वित, [[शीर्ष-सकर्मक ग्राफ]] होता है। इसे कभी-कभी चक्रीय ग्राफ कहा जाता है,<ref name="ds1"/>किन्तु इस शब्द के अन्य अर्थ भी होते हैं।
+[[File:Paley13.svg|thumb|240px|क्रम 13 का [[पाले ग्राफ]] सर्कुलेंट ग्राफ का उदाहरण है।]][[ ग्राफ सिद्धांत |ग्राफ सिद्धांत]] में, सर्कुलेंट ग्राफ [[अप्रत्यक्ष ग्राफ]] है, जो [[ग्राफ ऑटोमोर्फिज्म|समरूपता]] के [[चक्रीय समूह]] द्वारा क्रियान्वित, [[शीर्ष-सकर्मक ग्राफ]] होता है। इसे कभी-कभी चक्रीय ग्राफ कहा जाता है,<ref name="ds1"/>किन्तु इस पद के भिन्न-भिन्न अर्थ होते हैं।
 == समतुल्य परिभाषाएँ ==
-सर्कुलेंट ग्राफ़ का वर्णन विभिन्न समान प्रकारों से किया जा सकता है-<ref name="v04">{{citation|first=V.|last=Vilfred|contribution=On circulant graphs|title=Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001)|publisher=Alpha Science|editor1-first=R.|editor1-last=Balakrishnan|editor2-first=G.|editor2-last=Sethuraman|editor3-first=Robin J.|editor3-last=Wilson|year=2004|url=https://books.google.com/books?id=wG-08Lv8E-0C&pg=PA34|pages=34–36}}.</ref>
+सर्कुलेंट ग्राफ़ का वर्णन विभिन्न प्रकारों द्वारा किया जा सकता है-<ref name="v04">{{citation|first=V.|last=Vilfred|contribution=On circulant graphs|title=Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001)|publisher=Alpha Science|editor1-first=R.|editor1-last=Balakrishnan|editor2-first=G.|editor2-last=Sethuraman|editor3-first=Robin J.|editor3-last=Wilson|year=2004|url=https://books.google.com/books?id=wG-08Lv8E-0C&pg=PA34|pages=34–36}}.</ref>
-*ग्राफ़ के ऑटोमॉर्फिज़्म समूह में चक्रीय [[उपसमूह]] सम्मिलित होता है जो ग्राफ़ के शीर्ष पर [[समूह क्रिया (गणित)]] करता है। अन्य शब्दों में, ग्राफ़ में [[ऑटोमोर्फिज्म समूह]] होता है, जो इसके शीर्षों का चक्रीय क्रमचय है।
+*ग्राफ़ के स्वाकारिता समूह में चक्रीय [[उपसमूह]] सम्मिलित होता है जो ग्राफ़ के शीर्ष पर [[समूह क्रिया (गणित)]] करता है। अन्य शब्दों में, ग्राफ़ में [[ऑटोमोर्फिज्म समूह|स्वाकारिता समूह]] होता है, जो इसके शीर्षों का चक्रीय क्रमचय है।
-*ग्राफ़ में आसन्न मैट्रिक्स होता है जो [[ मैट्रिक्स की परिक्रमा | सर्कुलेंट मैट्रिक्स]]  है।
+*ग्राफ़ में आसन्न आव्यूह होता है जो [[ मैट्रिक्स की परिक्रमा | सर्कुलेंट आव्यूह]]  है।
 * ग्राफ़ के {{mvar|n}} शीर्षों को 0 से लेकर {{math|''n'' &minus; 1}} तक इस प्रकार क्रमांकित किया जा सकता है कि, यदि दो शीर्ष {{mvar|x}} और  {{math|(''x''&nbsp;+&nbsp;''d'')&nbsp;mod&nbsp;''n''}} आसन्न हैं, तो प्रत्येक दो शीर्षों {{mvar|z}} और {{math|(''z''&nbsp;+&nbsp;''d'')&nbsp;mod&nbsp;''n''}} को क्रमांकित किया जाता है। मॉड {{mvar|n}} आसन्न होते हैं।
-*ग्राफ़ निर्मित किया जा सकता है (संभवतः क्रॉसिंग के साथ) जिसमें इसके शीर्ष नियमित बहुभुज के शीर्षों पर स्थित होते हैं और बहुभुज की प्रत्येक घूर्णी समरूपता भी आरेखण की समरूपता होती है।
+*ग्राफ़ के शीर्ष नियमित बहुभुज के शीर्षों पर स्थित होते हैं और बहुभुज की प्रत्येक घूर्णी समरूपता आरेखण की समरूपता होती है।
 *ग्राफ, चक्रीय समूह का [[केली ग्राफ]] है।<ref>{{citation
   | last = Alspach | first = Brian | authorlink = Brian Alspach
@@ Line 25: / Line 25: @@
 == उदाहरण ==
-प्रत्येक [[चक्र ग्राफ]] सर्कुलेंट ग्राफ है, जैसा कि प्रत्येक [[क्राउन ग्राफ]] में 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''}} शतरंजबोर्ड के प्रत्येक वर्ग के लिए शीर्ष है और प्रत्येक दो वर्गों के लिए कोर है जो शतरंज के रूक के मध्य समान चलन में आगे बढ़ सकता है) सर्कुलेंट ग्राफ है। ऐसा इसलिए है क्योंकि इसकी समरूपता में उपसमूह के रूप में चक्रीय समूह ''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'' &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>
 == विशिष्ट उदाहरण ==
-<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> 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>\gcd(n, s_1, \ldots, s_k) = 1</math> है, तो ग्राफ <math>C_n^{s_1, \ldots, s_k}</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> 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>F_n</math> n-वें [[फाइबोनैचि संख्या]] है।
+** विशेष रूप से, <math>t(C_n^{1,2}) = nF_n^2 </math> जहाँ <math>F_n</math> n-वीं [[फाइबोनैचि संख्या]] है।
 ==स्व पूरक परिसंचारी==
-[[स्व-पूरक ग्राफ]] ऐसा ग्राफ है जिसमें प्रत्येक कोर को गैर-कोर द्वारा प्रतिस्थापित किया जाता है और इसके विपरीत [[ ग्राफ समरूपता | ग्राफ समरूपता]] का उत्पादन होता है।
+[[स्व-पूरक ग्राफ]] के प्रत्येक कोर को गैर-कोर द्वारा प्रतिस्थापित किया जाता है और इसके विपरीत [[ ग्राफ समरूपता | ग्राफ समरूपता]] का उत्पादन होता है।
-उदाहरण के लिए, पांच-शीर्ष चक्र ग्राफ, स्व-पूरक और सर्कुलेंट ग्राफ भी है। सामान्यतः प्राइम ऑर्डर का प्रत्येक पाले ग्राफ स्व-पूरक सर्कुलेंट ग्राफ होता है।<ref name="s62">{{Cite journal
+उदाहरण के लिए, पांच-शीर्ष चक्र ग्राफ, स्व-पूरक और सर्कुलेंट ग्राफ है। सामान्यतः प्राइम ऑर्डर का प्रत्येक पाले ग्राफ स्व-पूरक सर्कुलेंट ग्राफ होता है।<ref name="s62">{{Cite journal
   | last = Sachs | first = Horst | authorlink = Horst Sachs
   | mr = 0151953
@@ Line 54: / Line 54: @@
   | title = Über selbstkomplementäre Graphen
   | volume = 9
-  | year = 1962}}.</ref> [[होर्स्ट सैक्स]] ने प्रदर्शित किया कि यदि संख्या {{mvar|n}} में यह गुण है कि {{mvar|n}} का प्रत्येक अभाज्य गुणनखंड 1 मॉड्यूल 4 के सर्वांगसम है, तो {{mvar|n}} शीर्षों के साथ स्व-पूरक परिसंचारक उपस्थित है। उन्होंने अनुमान लगाया कि यह स्तिथि भी आवश्यक है, कि {{mvar|n}} का कोई अन्य मान स्व-पूरक परिसंचारक के अस्तित्व की अनुमति नहीं देता है।<ref name="v04" /><ref name="s62" />विलफ्रेड द्वारा प्रायः 40 वर्ष पश्चात यह अनुमान सिद्ध किया गया था।<ref name="v04" />
+  | year = 1962}}.</ref> [[होर्स्ट सैक्स|होर्स्ट साक्स]] ने प्रदर्शित किया कि यदि संख्या {{mvar|n}} में यह गुण है कि {{mvar|n}} का प्रत्येक अभाज्य गुणनखंड 1 मॉड्यूल 4 के सर्वांगसम है, तो {{mvar|n}} शीर्षों के साथ स्व-पूरक परिसंचारक उपस्थित होता है। उनका आकलन है, कि {{mvar|n}} का मान स्व-पूरक परिसंचारक के अस्तित्व की अनुमति प्रदान नहीं करता है।<ref name="v04" /><ref name="s62" />विलफ्रेड द्वारा प्रायः 40 वर्ष पश्चात यह आकलन सिद्ध किया गया था।<ref name="v04" />
-== Ádám का अनुमान ==
+== एडम का अनुमान ==
-एक सर्कुलेंट ग्राफ की सर्कुलेंट नंबरिंग को 0 से लेकर संख्याओं द्वारा ग्राफ के कोने की लेबलिंग के रूप में परिभाषित करें {{math|''n'' &minus; 1}} इस तरह से कि, यदि कुछ दो शीर्षों को क्रमांकित किया गया है {{mvar|x}} और {{mvar|y}} सन्निकट हैं, तो प्रत्येक दो शीर्षों को क्रमांकित किया गया है {{mvar|z}} और {{math|(''z'' &minus; ''x'' + ''y'') mod ''n''}} सटे हुए हैं। समतुल्य रूप से, एक सर्कुलेंट नंबरिंग वर्टिकल की एक संख्या है जिसके लिए ग्राफ का आसन्न मैट्रिक्स एक सर्कुलेंट मैट्रिक्स है।
+सर्कुलेंट ग्राफ की सर्कुलेंट नंबरिंग को 0 से लेकर {{math|''n'' &minus; 1}} संख्याओं द्वारा ग्राफ के शीर्षों की लेबलिंग के रूप में परिभाषित करें इस प्रकार कि, यदि दो शीर्ष  {{mvar|x}} और {{mvar|y}} आसन्न हैं, तो प्रत्येक दो शीर्ष {{mvar|z}} और {{math|(''z'' &minus; ''x'' + ''y'') mod ''n''}} भी आसन्न होते हैं। समतुल्य रूप से,  सर्कुलेंट नंबरिंग शीर्षों की संख्या है जिसके लिए ग्राफ का आसन्न आव्यूह, सर्कुलेंट आव्यूह है।
-होने देना {{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|G}} में शीर्ष {{mvar|x}} छह प्रतिवेशियों {{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
+टायडा का आकलन मात्र सर्कुलेंट ग्राफ के विशेष वर्ग पर विचार करके एडम के आकलन को परिष्कृत करता है, जिसमें आसन्न ग्राफ शीर्ष के मध्य के सभी विभेद शीर्षों की संख्याओं के लिए सह-अभाज्य होते हैं। इस परिष्कृत आकलन के अनुसार, इन विशेष सर्कुलेंट ग्राफ़ में यह गुण होना चाहिए कि उनकी सभी समरूपताएँ संख्याओं के मॉड्यूलो {{mvar|n}} के अंतर्निहित योगात्मक समूह की समरूपता हैं। यह 2001 और 2002 में दो समूहों द्वारा सिद्ध किया गया था।<ref>{{citation
   | last1 = Muzychuk | first1 = Mikhail
   | last2 = Klin | first2 = Mikhail
@@ Line 88: / Line 88: @@
 == एल्गोरिथम प्रश्न ==
-सर्कुलेंट ग्राफ़ के लिए एक बहुपद-समय मान्यता एल्गोरिथ्म है, और सर्कुलेंट ग्राफ़ के लिए आइसोमोर्फिज़्म समस्या को बहुपद समय में हल किया जा सकता है।<ref name="muz04">{{Cite journal
+परिसंचारी रेखांकन के लिए बहुपदी काल एल्गोरिथ्म होता है और परिसंचारी रेखांकन के लिए समरूपता समस्या को बहुपद काल में हल किया जा सकता है।<ref name="muz04">{{Cite journal
   | last1 = Muzychuk | first1 = Mikhail
   | mr = 2018956
@@ Line 115: / Line 115: @@
 ==बाहरी संबंध==
 *{{mathworld|title=Circulant Graph|urlname=CirculantGraph}}
-[[Category: ग्राफ परिवार]] [[Category: नियमित रेखांकन]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 26/04/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:ग्राफ परिवार]]
+[[Category:नियमित रेखांकन]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 10:45, 4 May 2023

Contents

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

उदाहरण

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

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

एडम का अनुमान

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

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 10:45, 4 May 2023

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

उदाहरण

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

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

एडम का अनुमान

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

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories