केज (ग्राफ सिद्धांत): Difference between revisions

From Vigyanwiki
No edit summary
 
(One intermediate revision by one other user not shown)
Line 180: Line 180:
* Royle, Gordon. [https://web.archive.org/web/20120730080521/http://mapleta.maths.uwa.edu.au/~gordon/remote/cages/index.html Cubic Cages] and [https://web.archive.org/web/20120802034729/http://mapleta.maths.uwa.edu.au/~gordon/remote/cages/allcages.html Higher valency cages]
* Royle, Gordon. [https://web.archive.org/web/20120730080521/http://mapleta.maths.uwa.edu.au/~gordon/remote/cages/index.html Cubic Cages] and [https://web.archive.org/web/20120802034729/http://mapleta.maths.uwa.edu.au/~gordon/remote/cages/allcages.html Higher valency cages]
*{{mathworld | title = Cage Graph | urlname = CageGraph}}
*{{mathworld | title = Cage Graph | urlname = CageGraph}}
[[Category: ग्राफ परिवार]] [[Category: नियमित रेखांकन]]


[[Category: Machine Translated Page]]
[[Category:Created On 08/05/2023]]
[[Category:Created On 08/05/2023]]
[[Category:Vigyan Ready]]
[[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:नियमित रेखांकन]]

Latest revision as of 09:51, 26 May 2023

टुट्टे (3,8)-केज.

लेखाचित्र सिद्धांत के गणित क्षेत्र में, केज एक नियमित लेखाचित्र होता है जिसमें इसकी परिधि (लेखाचित्र सिद्धांत) के लिए जितना संभव हो उतना कम कोणबिंदु (लेखाचित्र सिद्धांत) होता है।

औपचारिक रूप से, (r, g)-लेखाचित्र को एक लेखाचित्र (विच्छेद गणित) के रूप में परिभाषित किया गया है जिसमें प्रत्येक शीर्ष में यथार्थ r प्रतिवैस है, और जिसमें सबसे छोटे चक्र लेखाचित्र की लंबाई ठीक g है। एक (r, g)-केज (r, g)-लेखाचित्र है जिसमें सभी (r, g)-लेखाचित्र में सबसे कम संख्या में कोने होते हैं। (3, g)-केज को प्रायः g-केज कहा जाता है।

यह ज्ञात है कि (r, g)-लेखाचित्र के किसी भी संयोजन के लिए r ≥ 2 और g ≥ 3 उपस्थित है। इससे पता चलता है कि सभी (r, g)-केज उपस्थित हैं।

यदि मूर लेखाचित्र डिग्री के साथ r और परिधि g उपस्थित है, तो यह एक केज होना चाहिए। इसके अतिरिक्त, मूर लेखाचित्र के आकार की सीमाएं पिंजरों के लिए सामान्यीकृत होती हैं: विषम परिधि वाला कोई भी केज g कम से कम होना चाहिए

कोने, और कोई केज भी परिधि g के साथ कम से कम निम्न होना चाहिए

कोने। कोई (r, g)-लेखाचित्र सटीक रूप से इतने सारे कोने परिभाषा के अनुसार एक मूर लेखाचित्र है और इसलिए स्वचालित रूप से एक केज है।

किसी दिए गए संयोजन के लिए कई r और g केज उपस्थित हो सकते हैं। उदाहरण के लिए तीन गैर-समरूपी (3, 10)-केज हैं, प्रत्येक 70 शीर्षों के साथ: बलबन 10-केज, हैरी लेखाचित्र और हैरीज़-वोंग लेखाचित्र। लेकिन एक ही (3, 11)-केज है : बलबन 11-केज (112 सिरों के साथ)।

ज्ञात केज

एक 1-नियमित लेखाचित्र में कोई चक्र नहीं होता है, और एक आनुषंगिक 2-नियमित लेखाचित्र में उसके शीर्षों की संख्या के बराबर परिधि होती है, इसलिए केज केवल r ≥ 3 के लिए रुचि के होते हैं। (r,3)-केज एक पूर्ण लेखाचित्र Kr+1 है r+1 कोने पर, और (r,4)-केज 2r शीर्ष पर एक पूर्ण द्विदलीय लेखाचित्र Kr,r है।

उल्लेखनीय पिंजरों में सम्मिलित हैं:

ज्ञात (r, g) पिंजरों में कोने की संख्या, r> 2 और g> 2 के मूल्यों के लिए, प्रक्षेपी समतल और सामान्यीकृत बहुभुजों के अतिरिक्त, हैं:

g
r
3 4 5 6 7 8 9 10 11 12
3 4 6 10 14 24 30 58 70 112 126
4 5 8 19 26 67 80 728
5 6 10 30 42 170 2730
6 7 12 40 62 312 7812
7 8 14 50 90


अनंतस्पर्शी

g के बड़े मूल्यों के लिए, मूर बाउंड का तात्पर्य है कि कोने की संख्या कम से कम घातीय वृद्धि होनी चाहिए। समान रूप से, g, n के लघुगणक के अधिक से अधिक समानुपाती हो सकता है। अधिक यथार्थतः,

ऐसा माना जाता है कि यह बन्ध तंग या तंग (बोलोबस & ज़ेमेरीडी 2002) के करीब है। g पर सबसे अच्छी ज्ञात निचली सीमाएँ भी लघुगणकीय हैं, लेकिन एक छोटे स्थिर कारक के साथ (जिसका अर्थ है कि n अकेले घातीय रूप से बढ़ता है लेकिन मूर बाध्य की तुलना में उच्च दर पर)। विशेष रूप से, द्वारा परिभाषित रामानुजन रेखांकन का निर्माण लुबोत्ज़की, फिलिप्स & सरनाक (1988) सीमा को संतुष्ट करते हैं

लेज़ेबनिक, उस्तिमेंको & वोल्डर (1995) द्वारा इस सीमा में थोड़ा सुधार किया गया था।

यह संभावना नहीं है कि ये रेखांकन स्वयं केज हैं, लेकिन उनका अस्तित्व एक केज में आवश्यक शीर्षों की संख्या के लिए एक ऊपरी सीमा प्रदान करता है।

संदर्भ


बाहरी संबंध