दूरी-नियमित ग्राफ: Difference between revisions
(Created page with "{{short description|Graph property}} {{refimprove|date=June 2009}} {{Graph families defined by their automorphisms}} ग्राफ़ सिद्धांत के ग...") |
No edit summary |
||
(4 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
{{short description|Graph property}} | {{short description|Graph property}} | ||
{{Graph families defined by their automorphisms}} | {{Graph families defined by their automorphisms}} | ||
ग्राफ़ सिद्धांत के [[गणितीय]] क्षेत्र में | ग्राफ़ सिद्धांत के [[गणितीय]] क्षेत्र में दूरी-[[नियमित ग्राफ]] मुख्यतः नियमित ग्राफ़ का स्वरूप हैं जैसे कि किन्हीं भी दो अक्षों (ग्राफ़ सिद्धांत) के लिए {{mvar|v}} और {{mvar|w}}, दूरियों पर शीर्षों की संख्या (ग्राफ़ सिद्धांत) {{mvar|j}} से {{mvar|v}} और दूरी पर {{mvar|k}} से {{mvar|w}} पर {{mvar|j}}, {{mvar|k}}, और बीच की दूरी {{mvar|v}} और {{mvar|w}} पर निर्भर करती है। | ||
कुछ लेखक इस परिभाषा से पूर्ण रेखांकन और | कुछ लेखक इस परिभाषा से पूर्ण रेखांकन और विसंयोजन किए गए रेखांकन को बहिष्कृत कर देते हैं। | ||
प्रत्येक [[दूरी-सकर्मक ग्राफ]] दूरी | प्रत्येक [[दूरी-सकर्मक ग्राफ]] नियमित दूरी के समान होती हैं। वास्तव में दूरी-नियमित रेखांकन को दूरी-सकर्मक रेखांकन के संयोजी सामान्यीकरण के रूप में प्रस्तुत किया गया था, जिसमें आवश्यक रूप से बड़े [[ग्राफ ऑटोमोर्फिज्म]] के बिना इसके बाद के संख्यात्मक नियमितता के गुण होते हैं। | ||
== प्रतिच्छेदन | == प्रतिच्छेदन सारणी == | ||
यह पता चला है कि | यह पता चला है कि ग्राफ <math>G </math> व्यास का <math>d </math> दूरी-नियमित है, इस प्रकार यह केवल पूर्णांकों की सारणी <math>\{ b_0, b_1, \ldots, b_{d-1}; c_1, \ldots, c_d \} </math> है तो इस प्रकार सभी मानों के लिए <math>1 \leq j \leq d </math>, <math>b_j </math> के समीपस्थ संख्याओं का मान देता है, जो <math>u </math> दूरी पर <math>j+1 </math> से <math>v </math> और <math>c_j </math> के समीपस्थ की संख्या देता है। इस कारण <math>u </math> दूरी पर <math>j - 1 </math> से <math>v </math> किसी भी जोड़ी के शीर्ष के लिए <math>u </math> और <math>v </math> दूरी पर <math>j </math> पर <math>G </math> द्वारा प्रकट होता हैं। इस प्रकार दूरी-नियमित ग्राफ़ की विशेषता वाले पूर्णांकों की सरणी को इसके प्रतिच्छेदन सरणी के रूप में जाना जाता है। | ||
=== कोस्पेक्ट्रल दूरी-नियमित रेखांकन === | === कोस्पेक्ट्रल दूरी-नियमित रेखांकन === | ||
संयोजित दूरी-नियमित ग्राफ़ की जोड़ी [[स्पेक्ट्रल ग्राफ सिद्धांत]] पर निर्भर करती है इस कारण यदि इसमें अंतःखण्ड सारणिक है। | |||
इस प्रकार किसी दूरी-नियमित ग्राफ़ को जब विसंयोजित किया जाता है तो इस कारण यह कोस्पेक्ट्रल दूरी-नियमित ग्राफ़ के लिए ग्राफ़ संघ के रूप में निरूपित किया जाता है। | |||
== गुण == | == गुण == | ||
कल्पना | इस प्रकार कल्पना करने पर यदि <math>G </math> डिग्री का जुड़ा हुआ भाग दूरी-नियमित ग्राफ को प्रकट करता हैं (ग्राफ सिद्धांत) <math>k</math> अंतःखण्ड सरणी के साथ <math>\{ b_0, b_1, \ldots, b_{d-1}; c_1, \ldots, c_d \} </math>का मान प्रकट करता हैं तो इस कारण सभी के लिए <math>0 \leq j \leq d </math>: का मान <math>G_{j} </math> द्वारा निरूपित किया जाता हैं, यहाँ पर <math>k_{j} </math>आसन्न सारणिक के साथ नियमित ग्राफ <math>A_j </math> पर शीर्षों के जोड़े को जोड़कर बनाया गया हैं जिसके फलस्वरूप <math>G </math> दूरी पर <math>j </math>, और <math>a_j </math> के समीपस्थ संख्या को निरूपित करते हैं। इस प्रकार <math>u </math> दूरी पर <math>j </math> से <math>v </math> किसी भी जोड़ी के शीर्ष के लिए <math>u </math> और <math>v </math> दूरी पर <math>j </math> पर <math>G </math> का मान प्रकट किया जाता हैं। | ||
=== ग्राफ-सैद्धांतिक गुण === | === ग्राफ-सैद्धांतिक गुण === | ||
Line 27: | Line 26: | ||
=== स्पेक्ट्रल गुण === | === स्पेक्ट्रल गुण === | ||
*<math>k \leq \frac{1}{2} (m - 1)(m + 2)</math> किसी भी | *<math>k \leq \frac{1}{2} (m - 1)(m + 2)</math> किसी भी आइजन मान की बहुलता के लिए <math>m > 1</math> का मान <math>G</math> द्वारा प्रकट होता हैं, जब तक <math>G</math> पूर्ण बहुपक्षीय ग्राफ है। | ||
*<math>d \leq 3m - 4</math> किसी भी | *<math>d \leq 3m - 4</math> किसी भी आइजन मान की बहुलता के लिए <math>m > 1</math> का <math>G</math>, जब तक <math>G</math> चक्र ग्राफ या पूर्ण रूप से बहुपक्षीय ग्राफ को प्रकट करता है। | ||
*<math>\lambda \in \{ \pm k \}</math> अगर <math>\lambda</math> का | *<math>\lambda \in \{ \pm k \}</math> अगर <math>\lambda</math> का साधारण आइगेनवैल्यू <math>G </math> है। | ||
*<math>G </math> है <math>d + 1 </math> अलग | *<math>G </math> है <math>d + 1 </math> अलग आइगेनवैल्यू हैं। | ||
अगर <math>G </math> [[मजबूत नियमित ग्राफ]] है, फिर <math>n \leq 4m - 1</math> और <math>k \leq 2m - 1</math>. | अगर <math>G </math> [[मजबूत नियमित ग्राफ]] है, फिर <math>n \leq 4m - 1</math> और <math>k \leq 2m - 1</math>. | ||
== उदाहरण == | == उदाहरण == | ||
[[File:Klein-map.png|thumb|डिग्री 7 [[क्लेन ग्राफ]] और संबंधित मानचित्र जीनस 3 की | [[File:Klein-map.png|thumb|डिग्री 7 [[क्लेन ग्राफ]] और संबंधित मानचित्र जीनस 3 की ओरिएंटेबल सतह में एम्बेडेड है। यह ग्राफ इंटरसेक्शन सरणी {7,4,1;1,2,7} और ऑटोमोर्फिज्म समूह पीजीएल (2,7) के साथ नियमित रूप से दूरी है।]]दूरी-नियमित रेखांकन के कुछ पहले उदाहरणों में सम्मिलित हैं: | ||
* | * पूर्ण रेखांकन | ||
* चक्र | * चक्र रेखांकन | ||
* विषम | * विषम रेखांकन | ||
* मूर | * मूर रेखांकन | ||
* | * समीपस्थ पॉलीगॉन नियमित समीपस्थ पॉलीगॉन का कोलीनियरिटी ग्राफ़ | ||
* [[वेल्स ग्राफ]] और [[सिल्वेस्टर ग्राफ]] | * [[वेल्स ग्राफ]] और [[सिल्वेस्टर ग्राफ]] | ||
* | * | ||
* व्यास के | * व्यास के शक्तिशाली नियमित रेखांकन <math>2</math> | ||
== दूरी-नियमित रेखांकन का वर्गीकरण == | == दूरी-नियमित रेखांकन का वर्गीकरण == | ||
किसी भी संयोजकता के केवल सूक्ष्म रूप से कई अलग-अलग जुड़े हुए दूरी-नियमित ग्राफ़ | किसी भी संयोजकता के केवल सूक्ष्म रूप से कई अलग-अलग जुड़े हुए दूरी-नियमित ग्राफ़ <math>k > 2</math> हैं।<ref>{{Cite journal|last1=Bang|first1=S.|last2=Dubickas|first2=A.|last3=Koolen|first3=J. H.|last4=Moulton|first4=V.|date=2015-01-10|title=दो से अधिक स्थिर संयोजकता के केवल बहुत अधिक दूरी-नियमित ग्राफ़ हैं|journal=[[Advances in Mathematics]]|volume=269|issue=Supplement C|pages=1–55|doi=10.1016/j.aim.2014.09.025|doi-access=free|arxiv=0909.5253|s2cid=18869283}}</ref> इसी प्रकार किसी भी दिए गए आइजन मान बहुलता के साथ केवल बहुत ही अलग-अलग जुड़े दूरी-नियमित ग्राफ़ <math>m > 2</math> हैं। <ref>{{Cite journal|last=Godsil|first=C. D.|date=1988-12-01|title=दूरी-नियमित रेखांकन के व्यास को बाउंड करना|journal=[[Combinatorica]]|language=en|volume=8|issue=4|pages=333–343|doi=10.1007/BF02189090|s2cid=206813795|issn=0209-9683}}</ref> (पूर्ण बहुपक्षीय रेखांकन के अपवाद के साथ होता हैं)। | ||
इसी | |||
=== घन दूरी-नियमित रेखांकन === | === घन दूरी-नियमित रेखांकन === | ||
[[क्यूबिक ग्राफ]] | [[क्यूबिक ग्राफ]] दूरी-नियमित ग्राफ़ को पूर्ण रूप से वर्गीकृत किया जाता है। | ||
13 विशिष्ट क्यूबिक दूरी-नियमित ग्राफ़ पूर्ण ग्राफ़ हैं | | 13 विशिष्ट क्यूबिक दूरी-नियमित ग्राफ़ पूर्ण ग्राफ़ हैं | K<sub>4</sub>(या [[टेट्राहेड्रल ग्राफ]]), पूर्ण द्विदलीय ग्राफ या K<sub>3,3</sub>, [[पीटरसन ग्राफ]], [[क्यूबिकल ग्राफ]], [[ हीवुड ग्राफ |हीवुड ग्राफ]] , [[पप्पू ग्राफ]], [[कॉक्सेटर ग्राफ]], टुट्टे-कॉक्सेटर ग्राफ, [[डोडेकाहेड्रल ग्राफ]], [[Desargues ग्राफ]], [[सभी 12-पिंजरे]], बिग्स-स्मिथ ग्राफ और [[फोस्टर ग्राफ]] द्वारा प्राप्त होता हैं। | ||
==संदर्भ== | ==संदर्भ== | ||
{{Reflist}} | {{Reflist}} | ||
Line 63: | Line 61: | ||
* {{cite book|last=Godsil|first=C. D.|author-link=Chris Godsil|title=Algebraic Combinatorics|series=Chapman and Hall Mathematics Series|publisher=Chapman and Hall|location=New York|year=1993|isbn=978-0-412-04131-0|mr=1220704}} | * {{cite book|last=Godsil|first=C. D.|author-link=Chris Godsil|title=Algebraic Combinatorics|series=Chapman and Hall Mathematics Series|publisher=Chapman and Hall|location=New York|year=1993|isbn=978-0-412-04131-0|mr=1220704}} | ||
{{DEFAULTSORT:Distance-Regular Graph}} | {{DEFAULTSORT:Distance-Regular Graph}} | ||
[[Category: | [[Category:CS1 English-language sources (en)]] | ||
[[Category:Created On 08/05/2023]] | [[Category:Created On 08/05/2023|Distance-Regular Graph]] | ||
[[Category:Lua-based templates|Distance-Regular Graph]] | |||
[[Category:Machine Translated Page|Distance-Regular Graph]] | |||
[[Category:Pages with script errors|Distance-Regular Graph]] | |||
[[Category:Templates Vigyan Ready|Distance-Regular Graph]] | |||
[[Category:Templates that add a tracking category|Distance-Regular Graph]] | |||
[[Category:Templates that generate short descriptions|Distance-Regular Graph]] | |||
[[Category:Templates using TemplateData|Distance-Regular Graph]] | |||
[[Category:ग्राफ परिवार|Distance-Regular Graph]] | |||
[[Category:नियमित रेखांकन|Distance-Regular Graph]] | |||
[[Category:बीजगणितीय ग्राफ सिद्धांत|Distance-Regular Graph]] |
Latest revision as of 15:14, 24 May 2023
Graph families defined by their automorphisms | ||||
---|---|---|---|---|
distance-transitive | → | distance-regular | ← | strongly regular |
↓ | ||||
symmetric (arc-transitive) | ← | [[symmetric graph|t-transitive, t ≥ 2]] | skew-symmetric | |
↓ | ||||
(if connected) vertex- and edge-transitive |
→ | edge-transitive and regular | → | edge-transitive |
↓ | ↓ | ↓ | ||
vertex-transitive | → | regular | → | (if bipartite) biregular |
↑ | ||||
Cayley graph | ← | zero-symmetric | asymmetric |
ग्राफ़ सिद्धांत के गणितीय क्षेत्र में दूरी-नियमित ग्राफ मुख्यतः नियमित ग्राफ़ का स्वरूप हैं जैसे कि किन्हीं भी दो अक्षों (ग्राफ़ सिद्धांत) के लिए v और w, दूरियों पर शीर्षों की संख्या (ग्राफ़ सिद्धांत) j से v और दूरी पर k से w पर j, k, और बीच की दूरी v और w पर निर्भर करती है।
कुछ लेखक इस परिभाषा से पूर्ण रेखांकन और विसंयोजन किए गए रेखांकन को बहिष्कृत कर देते हैं।
प्रत्येक दूरी-सकर्मक ग्राफ नियमित दूरी के समान होती हैं। वास्तव में दूरी-नियमित रेखांकन को दूरी-सकर्मक रेखांकन के संयोजी सामान्यीकरण के रूप में प्रस्तुत किया गया था, जिसमें आवश्यक रूप से बड़े ग्राफ ऑटोमोर्फिज्म के बिना इसके बाद के संख्यात्मक नियमितता के गुण होते हैं।
प्रतिच्छेदन सारणी
यह पता चला है कि ग्राफ व्यास का दूरी-नियमित है, इस प्रकार यह केवल पूर्णांकों की सारणी है तो इस प्रकार सभी मानों के लिए , के समीपस्थ संख्याओं का मान देता है, जो दूरी पर से और के समीपस्थ की संख्या देता है। इस कारण दूरी पर से किसी भी जोड़ी के शीर्ष के लिए और दूरी पर पर द्वारा प्रकट होता हैं। इस प्रकार दूरी-नियमित ग्राफ़ की विशेषता वाले पूर्णांकों की सरणी को इसके प्रतिच्छेदन सरणी के रूप में जाना जाता है।
कोस्पेक्ट्रल दूरी-नियमित रेखांकन
संयोजित दूरी-नियमित ग्राफ़ की जोड़ी स्पेक्ट्रल ग्राफ सिद्धांत पर निर्भर करती है इस कारण यदि इसमें अंतःखण्ड सारणिक है।
इस प्रकार किसी दूरी-नियमित ग्राफ़ को जब विसंयोजित किया जाता है तो इस कारण यह कोस्पेक्ट्रल दूरी-नियमित ग्राफ़ के लिए ग्राफ़ संघ के रूप में निरूपित किया जाता है।
गुण
इस प्रकार कल्पना करने पर यदि डिग्री का जुड़ा हुआ भाग दूरी-नियमित ग्राफ को प्रकट करता हैं (ग्राफ सिद्धांत) अंतःखण्ड सरणी के साथ का मान प्रकट करता हैं तो इस कारण सभी के लिए : का मान द्वारा निरूपित किया जाता हैं, यहाँ पर आसन्न सारणिक के साथ नियमित ग्राफ पर शीर्षों के जोड़े को जोड़कर बनाया गया हैं जिसके फलस्वरूप दूरी पर , और के समीपस्थ संख्या को निरूपित करते हैं। इस प्रकार दूरी पर से किसी भी जोड़ी के शीर्ष के लिए और दूरी पर पर का मान प्रकट किया जाता हैं।
ग्राफ-सैद्धांतिक गुण
- सभी के लिए .
- और .
स्पेक्ट्रल गुण
- किसी भी आइजन मान की बहुलता के लिए का मान द्वारा प्रकट होता हैं, जब तक पूर्ण बहुपक्षीय ग्राफ है।
- किसी भी आइजन मान की बहुलता के लिए का , जब तक चक्र ग्राफ या पूर्ण रूप से बहुपक्षीय ग्राफ को प्रकट करता है।
- अगर का साधारण आइगेनवैल्यू है।
- है अलग आइगेनवैल्यू हैं।
अगर मजबूत नियमित ग्राफ है, फिर और .
उदाहरण
दूरी-नियमित रेखांकन के कुछ पहले उदाहरणों में सम्मिलित हैं:
- पूर्ण रेखांकन
- चक्र रेखांकन
- विषम रेखांकन
- मूर रेखांकन
- समीपस्थ पॉलीगॉन नियमित समीपस्थ पॉलीगॉन का कोलीनियरिटी ग्राफ़
- वेल्स ग्राफ और सिल्वेस्टर ग्राफ
- व्यास के शक्तिशाली नियमित रेखांकन
दूरी-नियमित रेखांकन का वर्गीकरण
किसी भी संयोजकता के केवल सूक्ष्म रूप से कई अलग-अलग जुड़े हुए दूरी-नियमित ग्राफ़ हैं।[1] इसी प्रकार किसी भी दिए गए आइजन मान बहुलता के साथ केवल बहुत ही अलग-अलग जुड़े दूरी-नियमित ग्राफ़ हैं। [2] (पूर्ण बहुपक्षीय रेखांकन के अपवाद के साथ होता हैं)।
घन दूरी-नियमित रेखांकन
क्यूबिक ग्राफ दूरी-नियमित ग्राफ़ को पूर्ण रूप से वर्गीकृत किया जाता है।
13 विशिष्ट क्यूबिक दूरी-नियमित ग्राफ़ पूर्ण ग्राफ़ हैं | K4(या टेट्राहेड्रल ग्राफ), पूर्ण द्विदलीय ग्राफ या K3,3, पीटरसन ग्राफ, क्यूबिकल ग्राफ, हीवुड ग्राफ , पप्पू ग्राफ, कॉक्सेटर ग्राफ, टुट्टे-कॉक्सेटर ग्राफ, डोडेकाहेड्रल ग्राफ, Desargues ग्राफ, सभी 12-पिंजरे, बिग्स-स्मिथ ग्राफ और फोस्टर ग्राफ द्वारा प्राप्त होता हैं।
संदर्भ
- ↑ Bang, S.; Dubickas, A.; Koolen, J. H.; Moulton, V. (2015-01-10). "दो से अधिक स्थिर संयोजकता के केवल बहुत अधिक दूरी-नियमित ग्राफ़ हैं". Advances in Mathematics. 269 (Supplement C): 1–55. arXiv:0909.5253. doi:10.1016/j.aim.2014.09.025. S2CID 18869283.
- ↑ Godsil, C. D. (1988-12-01). "दूरी-नियमित रेखांकन के व्यास को बाउंड करना". Combinatorica (in English). 8 (4): 333–343. doi:10.1007/BF02189090. ISSN 0209-9683. S2CID 206813795.
अग्रिम पठन
- Godsil, C. D. (1993). Algebraic Combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall. ISBN 978-0-412-04131-0. MR 1220704.