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

From Vigyanwiki
(Created page with "{{Short description|Regular graph with fewest possible nodes for its girth}} Image:Tutte eight cage.svg|thumb|right|द ऑल-कॉक्सेटर ग्राफ | ऑ...")
 
(text)
Line 1: Line 1:
{{Short description|Regular graph with fewest possible nodes for its girth}}
{{Short description|Regular graph with fewest possible nodes for its girth}}
[[Image:Tutte eight cage.svg|thumb|right|द ऑल-कॉक्सेटर ग्राफ | ऑल {{nowrap|{{math|(3,8)}}-cage}}.]]ग्राफ़ सिद्धांत के गणित क्षेत्र में, एक पिंजरा एक [[नियमित ग्राफ]]होता है जिसमें इसकी परिधि (ग्राफ़ सिद्धांत) के लिए जितना संभव हो उतना कम वर्टेक्स (ग्राफ़ सिद्धांत) होता है।
[[Image:Tutte eight cage.svg|thumb|right| टुट्टे {{nowrap|{{math|(3,8)}}-केज}}.]]लेखाचित्र सिद्धांत के गणित क्षेत्र में, केज एक [[नियमित ग्राफ|नियमित]] लेखाचित्र होता है जिसमें इसकी परिधि (लेखाचित्र सिद्धांत) के लिए जितना संभव हो उतना कम कोणबिंदु (लेखाचित्र सिद्धांत) होता है।


औपचारिक रूप से, {{nowrap|{{math|(''r'', ''g'')}}-graph}} को एक ग्राफ़ (विच्छेद गणित) के रूप में परिभाषित किया गया है जिसमें प्रत्येक शीर्ष में सटीक है {{mvar|r}} पड़ोसी, और जिसमें सबसे छोटे [[चक्र ग्राफ]] की लंबाई ठीक है {{mvar|g}}.
औपचारिक रूप से, {{nowrap|{{math|(''r'', ''g'')}}-लेखाचित्र}} को एक लेखाचित्र (विच्छेद गणित) के रूप में परिभाषित किया गया है जिसमें प्रत्येक शीर्ष में यथार्थ {{mvar|r}} प्रतिवैस है, और जिसमें सबसे छोटे [[चक्र ग्राफ|चक्र लेखाचित्र]] की लंबाई ठीक {{mvar|g}} है। एक {{nowrap|{{math|(''r'', ''g'')}}-केज}} {{nowrap|{{math|(''r'', ''g'')}}-लेखाचित्र}} है जिसमें सभी {{nowrap|{{math|(''r'', ''g'')}}-लेखाचित्र}} में सबसे कम संख्या में कोने होते हैं। {{nowrap|{{math|(3, ''g'')}}-केज}} को प्रायः {{nowrap|{{mvar|g}}-केज}} कहा जाता है।
एक {{nowrap|{{math|(''r'', ''g'')}}-cage}} एक {{nowrap|{{math|(''r'', ''g'')}}-graph}} सबसे कम संभव शीर्षों के साथ, सभी के बीच {{nowrap|{{math|(''r'', ''g'')}}-graphs}}. ए {{nowrap|{{math|(3, ''g'')}}-cage}} को अक्सर कहा जाता है {{nowrap|{{mvar|g}}-cage}}.


यह ज्ञात है कि {{nowrap|{{math|(''r'', ''g'')}}-graph}} के किसी भी संयोजन के लिए मौजूद है {{nowrap|{{math|''r'' ≥ 2}}}} और {{nowrap|{{math|''g'' ≥ 3}}}}. यह सब इस प्रकार है {{nowrap|{{math|(''r'', ''g'')}}-cages}} अस्तित्व।
यह ज्ञात है कि {{nowrap|{{math|(''r'', ''g'')}}-लेखाचित्र}} के किसी भी संयोजन के लिए {{nowrap|{{math|''r'' ≥ 2}}}} और {{nowrap|{{math|''g'' ≥ 3}}}} उपस्थित है। इससे पता चलता है कि सभी {{nowrap|{{math|(''r'', ''g'')}}-केज}} उपस्थित हैं। 


यदि [[मूर ग्राफ]] डिग्री के साथ मौजूद है {{mvar|r}} और परिधि {{mvar|g}}, यह एक पिंजरा होना चाहिए। इसके अलावा, मूर ग्राफ के आकार की सीमाएं पिंजरों के लिए सामान्यीकृत होती हैं: विषम परिधि वाला कोई भी पिंजरा {{mvar|g}} कम से कम होना चाहिए
यदि [[मूर ग्राफ|मूर लेखाचित्र]] डिग्री के साथ {{mvar|r}} और परिधि {{mvar|g}} उपस्थित है, तो यह एक केज होना चाहिए। इसके अतिरिक्त, मूर लेखाचित्र के आकार की सीमाएं पिंजरों के लिए सामान्यीकृत होती हैं: विषम परिधि वाला कोई भी केज {{mvar|g}} कम से कम होना चाहिए
:<math>1+r\sum_{i=0}^{(g-3)/2}(r-1)^i</math>
:<math>1+r\sum_{i=0}^{(g-3)/2}(r-1)^i</math>
शिखर, और कोई पिंजरा भी परिधि के साथ {{mvar|g}} कम से कम होना चाहिए
कोने, और कोई केज भी परिधि {{mvar|g}} के साथ कम से कम निम्न होना चाहिए
:<math>2\sum_{i=0}^{(g-2)/2}(r-1)^i</math>
:<math>2\sum_{i=0}^{(g-2)/2}(r-1)^i</math>
शिखर। कोई {{nowrap|{{math|(''r'', ''g'')}}-graph}} सटीक रूप से इतने सारे कोने परिभाषा के अनुसार एक मूर ग्राफ है और इसलिए स्वचालित रूप से एक पिंजरा है।
कोने। कोई {{nowrap|{{math|(''r'', ''g'')}}-लेखाचित्र}} सटीक रूप से इतने सारे कोने परिभाषा के अनुसार एक मूर लेखाचित्र है और इसलिए स्वचालित रूप से एक केज है।


किसी दिए गए संयोजन के लिए कई पिंजरे मौजूद हो सकते हैं {{mvar|r}} और {{mvar|g}}. उदाहरण के लिए तीन गैर-समरूपी हैं {{nowrap|{{math|(3, 10)}}-cages}}, प्रत्येक 70 शीर्षों के साथ: बलबन 10-पिंजरा, [[हैरी ग्राफ]] और हैरीज़-वोंग ग्राफ़। लेकिन एक ही है {{nowrap|{{math|(3, 11)}}-cage}}: बलबन 11-पिंजरा (112 सिरों के साथ)।
किसी दिए गए संयोजन के लिए कई {{mvar|r}} और {{mvar|g}} केज उपस्थित हो सकते हैं। उदाहरण के लिए तीन गैर-समरूपी {{nowrap|{{math|(3, 10)}}-केज}} हैं, प्रत्येक 70 शीर्षों के साथ: बलबन 10-केज, [[हैरी ग्राफ|हैरी लेखाचित्र]] और हैरीज़-वोंग लेखाचित्र। लेकिन एक ही {{nowrap|{{math|(3, 11)}}-केज}} है : बलबन 11-केज (112 सिरों के साथ)।


== ज्ञात पिंजरे ==
== ज्ञात केज ==
एक 1-नियमित ग्राफ़ में कोई चक्र नहीं होता है, और एक कनेक्टेड 2-नियमित ग्राफ़ में उसके शीर्षों की संख्या के बराबर परिधि होती है, इसलिए पिंजरे केवल r ≥ 3 के लिए दिलचस्प होते हैं। (r,3)-पिंजरा एक पूर्ण ग्राफ़ K है<sub>''r''+1</sub> r+1 कोने पर, और (r,4)-पिंजरा एक [[पूर्ण द्विदलीय ग्राफ]] K है<sub>''r'',''r''</sub> 2r शीर्ष पर।
एक 1-नियमित लेखाचित्र में कोई चक्र नहीं होता है, और एक आनुषंगिक 2-नियमित लेखाचित्र में उसके शीर्षों की संख्या के बराबर परिधि होती है, इसलिए केज केवल r ≥ 3 के लिए रुचि के होते हैं। (r,3)-केज एक पूर्ण लेखाचित्र K<sub>''r''+1</sub> है r+1 कोने पर, और (r,4)-केज 2r शीर्ष पर एक [[पूर्ण द्विदलीय ग्राफ|पूर्ण द्विदलीय लेखाचित्र]] K<sub>''r'',''r''</sub> है।


उल्लेखनीय पिंजरों में शामिल हैं:
उल्लेखनीय पिंजरों में सम्मिलित हैं:
* (3,5)-पिंजरा: [[पीटरसन ग्राफ]], 10 कोने
* (3,5)-केज: [[पीटरसन ग्राफ|पीटरसन लेखाचित्र]], 10 कोने
* (3,6)-पिंजरा: [[हीवुड ग्राफ]], 14 कोने
* (3,6)-केज: [[हीवुड ग्राफ|हीवुड लेखाचित्र]], 14 कोने
* (3,7)-पिंजरा: [[ मैगी ग्राफ ]], 24 शीर्ष
* (3,7)-केज: [[ मैगी ग्राफ | मैगी लेखाचित्र]] , 24 शीर्ष
* (3,8)-पिंजरा: टुट्टे-कॉक्सेटर ग्राफ, 30 कोने
* (3,8)-केज: टुट्टे-कॉक्सेटर लेखाचित्र, 30 कोने
* (3,10)-पिंजरा: बलबन 10-पिंजरा, 70 शिखर
* (3,10)-केज: बलबन 10-केज, 70 कोने
* (3,11)-पिंजरा: बलबन 11-पिंजरा, 112 शिखर
* (3,11)-केज: बलबन 11-केज, 112 कोने
* (4,5)-पिंजरा: [[रॉबर्टसन ग्राफ]], 19 शिखर
* (4,5)-केज: [[रॉबर्टसन ग्राफ|रॉबर्टसन लेखाचित्र]], 19 कोने
* (7,5)-पिंजरा: हॉफमैन-सिंगलटन ग्राफ, 50 कोने।
* (7,5)-केज: हॉफमैन-सिंगलटन लेखाचित्र, 50 कोने।
* जब r − 1 एक प्रमुख शक्ति है, (r,6) पिंजड़े [[प्रक्षेपी विमान]]ों के आपतन ग्राफ हैं।
* जब r − 1 एक प्रमुख शक्ति होती है, (r,6) केज [[प्रक्षेपी विमान|प्रक्षेपी]] समतल के आपतन लेखाचित्र हैं।
* जब r − 1 एक प्रमुख शक्ति है, (r,8) और (r,12) पिंजरे [[सामान्यीकृत बहुभुज]] हैं।
* जब r − 1 एक प्रमुख शक्ति होती है, (r,8) और (r,12) केज [[सामान्यीकृत बहुभुज]] हैं।


ज्ञात (आर, जी) पिंजरों में कोने की संख्या, आर> 2 और जी> 2 के मूल्यों के लिए, प्रक्षेपी विमानों और सामान्यीकृत बहुभुजों के अलावा, हैं:
ज्ञात (r, g) पिंजरों में कोने की संख्या, r> 2 और g> 2 के मूल्यों के लिए, प्रक्षेपी समतल और सामान्यीकृत बहुभुजों के अतिरिक्त, हैं:
{| class="wikitable"   
{| class="wikitable"   
! {{diagonal split header|r|g}} || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12
! {{diagonal split header|r|g}} || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12
Line 51: Line 50:




== असिम्प्टोटिक्स ==
== अनंतस्पर्शी ==
जी के बड़े मूल्यों के लिए, मूर बाउंड का तात्पर्य है कि वर्टिकल की संख्या कम से कम घातीय वृद्धि होनी चाहिए। समान रूप से, g, n के लघुगणक के अधिक से अधिक समानुपाती हो सकता है। ज्यादा ठीक,
g के बड़े मूल्यों के लिए, मूर बाउंड का तात्पर्य है कि कोने की संख्या कम से कम घातीय वृद्धि होनी चाहिए। समान रूप से, g, n के लघुगणक के अधिक से अधिक समानुपाती हो सकता है। अधिक यथार्थतः,
:<math>g\le 2\log_{r-1} n + O(1).</math>
:<math>g\le 2\log_{r-1} n + O(1).</math>
ऐसा माना जाता है कि यह बन्ध तंग या तंग के करीब है {{harv|Bollobás|Szemerédi|2002}}. जी पर सबसे अच्छी ज्ञात निचली सीमाएँ भी लॉगरिदमिक हैं, लेकिन एक छोटे स्थिर कारक के साथ (जिसका अर्थ है कि एन अकेले घातीय रूप से बढ़ता है लेकिन मूर बाउंड की तुलना में उच्च दर पर)। विशेष रूप से, द्वारा परिभाषित रामानुजन रेखांकन का निर्माण {{harvtxt|Lubotzky|Phillips|Sarnak|1988}} सीमा को पूरा करें
ऐसा माना जाता है कि यह बन्ध तंग या तंग {{harv|बोलोबस|ज़ेमेरीडी|2002}} के करीब है। g पर सबसे अच्छी ज्ञात निचली सीमाएँ भी लघुगणकीय हैं, लेकिन एक छोटे स्थिर कारक के साथ (जिसका अर्थ है कि n अकेले घातीय रूप से बढ़ता है लेकिन मूर बाध्य की तुलना में उच्च दर पर)। विशेष रूप से, द्वारा परिभाषित रामानुजन रेखांकन का निर्माण {{harvtxt|लुबोत्ज़की|फिलिप्स|सरनाक|1988}} सीमा को संतुष्ट करते हैं
:<math>g\ge \frac{4}{3}\log_{r-1} n + O(1).</math> द्वारा इस सीमा में थोड़ा सुधार किया गया था {{harvtxt|Lazebnik|Ustimenko|Woldar|1995}}.
:<math>g\ge \frac{4}{3}\log_{r-1} n + O(1).</math>  
:{{harvtxt|लेज़ेबनिक|उस्तिमेंको|वोल्डर|1995}} द्वारा इस सीमा में थोड़ा सुधार किया गया था।


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


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

Revision as of 16:59, 21 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) द्वारा इस सीमा में थोड़ा सुधार किया गया था।

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

संदर्भ


बाहरी संबंध