साइकिल ग्राफ: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Graph with nodes connected in a closed chain}} {{About|connected, 2-regular graphs||Cyclic graph}} {{infobox graph | name = Cycle | automorphisms = {...") |
No edit summary |
||
| Line 12: | Line 12: | ||
}} | }} | ||
ग्राफ़ सिद्धांत में, एक चक्र ग्राफ़ या वृत्ताकार ग्राफ़ एक ग्राफ़ (असतत गणित) होता है जिसमें एक एकल चक्र (ग्राफ़ सिद्धांत) होता है, या दूसरे शब्दों में, | ग्राफ़ सिद्धांत में, एक चक्र ग्राफ़ या वृत्ताकार ग्राफ़ एक ऐसा ग्राफ़ (असतत गणित) होता है जिसमें एक एकल चक्र (ग्राफ़ सिद्धांत) होता है, या दूसरे शब्दों में, शीर्ष(ग्राफ़ सिद्धांत) की कुछ संख्या (कम से कम 3, यदि ग्राफ़ [[सरल ग्राफ]] है) एक बंद श्रृंखला में जुड़ा हुआ है। {{mvar|n}} शीर्षों वाले चक्र ग्राफ को {{mvar|C{{sub|n}}}} कहा जाता है।<ref>{{harvtxt|Diestel|2017}} p. 8, §1.3</ref> {{mvar|C{{sub|n}}}} में शीर्षों की संख्या किनारे (ग्राफ सिद्धांत) की संख्या के बराबर है, और प्रत्येक शीर्ष की [[डिग्री (ग्राफ सिद्धांत)]] 2 है; अर्थात्, प्रत्येक शीर्ष के ठीक दो किनारे आपस में जुड़े होते हैं। | ||
== शब्दावली == | == शब्दावली == | ||
चक्र ग्राफ के लिए कई समानार्थक शब्द हैं। इनमें सरल चक्र ग्राफ और चक्रीय ग्राफ सम्मिलित हैं, यद्यपि बाद वाले शब्द का प्रयोग बहुत कम होता है, क्योंकि यह उन ग्राफों को भी संदर्भित कर सकता है जो [[निर्देशित अचक्रीय ग्राफ]] को निर्देशित नहीं करते हैं। ग्राफ सिद्धांतकारों में, चक्र, बहुभुज, या ''n''-गॉन भी प्रायः उपयोग किए जाते हैं। 'n'-चक्र शब्द का प्रयोग कभी-कभी अन्य समायोजन में किया जाता है।<ref>{{cite journal |title=Problem 11707 |journal=Amer. Math. Monthly |volume=120 |issue=5 |pages = 469–476|date=May 2013 |doi=10.4169/amer.math.monthly.120.05.469|jstor=10.4169/amer.math.monthly.120.05.469 |s2cid=41161918 }}</ref> सम संख्याओं वाले चक्र को सम चक्र कहा जाता है; एक विषम संख्या वाले चक्र को एक विषम चक्र कहा जाता है। | |||
== गुण == | == गुण == | ||
| Line 28: | Line 28: | ||
इसके साथ ही: | इसके साथ ही: | ||
* चूंकि चक्र ग्राफ [[नियमित बहुभुज]] के रूप में [[ग्राफ ड्राइंग]] हो सकते हैं, | * चूंकि चक्र ग्राफ [[नियमित बहुभुज]] के रूप में [[ग्राफ ड्राइंग]] हो सकते हैं, n-चक्र का [[ऑटोमोर्फिज्म समूह]] n पक्षों वाले नियमित बहुभुज के समान होता है, ऑर्डर 2 n के [[डायहेड्रल समूह]]। विशेष रूप से, किसी भी शीर्ष को किसी अन्य शीर्ष पर और किसी भी किनारे को किसी भी किनारे पर ले जाने वाली समरूपता मौजूद होती है, इसलिए n-चक्र एक [[सममित ग्राफ]] है। | ||
[[प्लेटोनिक ग्राफ]]़ के समान, चक्र ग्राफ़ [[डायहेड्रॉन]] के कंकाल बनाते हैं। उनके दोहरे द्विध्रुव रेखांकन हैं, जो [[hosohedron]] के कंकाल बनाते हैं। | [[प्लेटोनिक ग्राफ]]़ के समान, चक्र ग्राफ़ [[डायहेड्रॉन]] के कंकाल बनाते हैं। उनके दोहरे द्विध्रुव रेखांकन हैं, जो [[hosohedron]] के कंकाल बनाते हैं। | ||
| Line 35: | Line 35: | ||
[[Image:DC8.png|frame|right|लंबाई 8 का एक निर्देशित चक्र ग्राफ]]एक निर्देशित चक्र ग्राफ एक चक्र ग्राफ का एक निर्देशित संस्करण है, जिसमें सभी किनारे एक ही दिशा में उन्मुख होते हैं। | [[Image:DC8.png|frame|right|लंबाई 8 का एक निर्देशित चक्र ग्राफ]]एक निर्देशित चक्र ग्राफ एक चक्र ग्राफ का एक निर्देशित संस्करण है, जिसमें सभी किनारे एक ही दिशा में उन्मुख होते हैं। | ||
एक [[निर्देशित ग्राफ]]़ में, किनारों का एक | एक [[निर्देशित ग्राफ]]़ में, किनारों का एक समूह जिसमें प्रत्येक निर्देशित चक्र से कम से कम एक किनारा (या 'आर्क') होता है, को [[फीडबैक आर्क सेट|फीडबैक आर्क समूह]] कहा जाता है। इसी तरह, प्रत्येक निर्देशित चक्र से कम से कम एक शीर्ष वाले वर्टिकल के समूह को [[फीडबैक वर्टेक्स सेट|फीडबैक शीर्षसमूह]] कहा जाता है। | ||
एक निर्देशित चक्र ग्राफ़ में एक समान इन-डिग्री 1 और एकसमान आउट-डिग्री 1 होता है। | एक निर्देशित चक्र ग्राफ़ में एक समान इन-डिग्री 1 और एकसमान आउट-डिग्री 1 होता है। | ||
| Line 46: | Line 46: | ||
* [[पूरा ग्राफ]] | * [[पूरा ग्राफ]] | ||
* [[सर्कुलेंट ग्राफ]] | * [[सर्कुलेंट ग्राफ]] | ||
* [[साइकिल ग्राफ (बीजगणित)]] | * [[साइकिल ग्राफ (बीजगणित)|चक्र ग्राफ (बीजगणित)]] | ||
* [[शून्य ग्राफ]] | * [[शून्य ग्राफ]] | ||
* [[पथ ग्राफ]] | * [[पथ ग्राफ]] | ||
| Line 59: | Line 59: | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
*{{MathWorld |urlname=CycleGraph |title=Cycle Graph}} (discussion of both 2-regular cycle graphs and the group-theoretic concept of [[cycle diagram]]s) | *{{MathWorld |urlname=CycleGraph |title=Cycle Graph}} (discussion of both 2-regular cycle graphs and the group-theoretic concept of [[cycle diagram]]s) | ||
*[[Luca Trevisan]], [http://in-theory.blogspot.com/2006/12/characters-and-expansion.html Characters and Expansion] | *[[Luca Trevisan]], [http://in-theory.blogspot.com/2006/12/characters-and-expansion.html Characters and Expansion]। | ||
[[Category: रेखांकन के पैरामीट्रिक परिवार]] [[Category: नियमित रेखांकन]] | [[Category: रेखांकन के पैरामीट्रिक परिवार]] [[Category: नियमित रेखांकन]] | ||
Revision as of 09:17, 26 March 2023
| Cycle | |
|---|---|
| Girth | n |
| Automorphisms | 2n (Dn) |
| Chromatic number | 3 if n is odd 2 otherwise |
| Chromatic index | 3 if n is odd 2 otherwise |
| Spectrum | [1] |
| Properties | 2-regular Vertex-transitive Edge-transitive Unit distance Hamiltonian Eulerian |
| Notation | Cn |
| Table of graphs and parameters | |
ग्राफ़ सिद्धांत में, एक चक्र ग्राफ़ या वृत्ताकार ग्राफ़ एक ऐसा ग्राफ़ (असतत गणित) होता है जिसमें एक एकल चक्र (ग्राफ़ सिद्धांत) होता है, या दूसरे शब्दों में, शीर्ष(ग्राफ़ सिद्धांत) की कुछ संख्या (कम से कम 3, यदि ग्राफ़ सरल ग्राफ है) एक बंद श्रृंखला में जुड़ा हुआ है। n शीर्षों वाले चक्र ग्राफ को Cn कहा जाता है।[2] Cn में शीर्षों की संख्या किनारे (ग्राफ सिद्धांत) की संख्या के बराबर है, और प्रत्येक शीर्ष की डिग्री (ग्राफ सिद्धांत) 2 है; अर्थात्, प्रत्येक शीर्ष के ठीक दो किनारे आपस में जुड़े होते हैं।
शब्दावली
चक्र ग्राफ के लिए कई समानार्थक शब्द हैं। इनमें सरल चक्र ग्राफ और चक्रीय ग्राफ सम्मिलित हैं, यद्यपि बाद वाले शब्द का प्रयोग बहुत कम होता है, क्योंकि यह उन ग्राफों को भी संदर्भित कर सकता है जो निर्देशित अचक्रीय ग्राफ को निर्देशित नहीं करते हैं। ग्राफ सिद्धांतकारों में, चक्र, बहुभुज, या n-गॉन भी प्रायः उपयोग किए जाते हैं। 'n'-चक्र शब्द का प्रयोग कभी-कभी अन्य समायोजन में किया जाता है।[3] सम संख्याओं वाले चक्र को सम चक्र कहा जाता है; एक विषम संख्या वाले चक्र को एक विषम चक्र कहा जाता है।
गुण
एक चक्र ग्राफ है:
- के-एज रंगीन|2-एज कलरेबल, अगर और केवल अगर इसमें वर्टिकल की संख्या सम है
- नियमित ग्राफ|2-नियमित
- द्विदलीय ग्राफ|2-शीर्ष रंगीन, यदि और केवल यदि इसमें शीर्षों की संख्या सम है। अधिक आम तौर पर, एक ग्राफ द्विदलीय होता है यदि और केवल यदि इसमें कोई विषम चक्र न हो (डेनेस कोनिग | कोनिग, 1936)।
- जुड़ा हुआ ग्राफ
- यूलेरियन ग्राफ
- हैमिल्टनियन ग्राफ
- एक इकाई दूरी ग्राफ
इसके साथ ही:
- चूंकि चक्र ग्राफ नियमित बहुभुज के रूप में ग्राफ ड्राइंग हो सकते हैं, n-चक्र का ऑटोमोर्फिज्म समूह n पक्षों वाले नियमित बहुभुज के समान होता है, ऑर्डर 2 n के डायहेड्रल समूह। विशेष रूप से, किसी भी शीर्ष को किसी अन्य शीर्ष पर और किसी भी किनारे को किसी भी किनारे पर ले जाने वाली समरूपता मौजूद होती है, इसलिए n-चक्र एक सममित ग्राफ है।
प्लेटोनिक ग्राफ़ के समान, चक्र ग्राफ़ डायहेड्रॉन के कंकाल बनाते हैं। उनके दोहरे द्विध्रुव रेखांकन हैं, जो hosohedron के कंकाल बनाते हैं।
निर्देशित चक्र ग्राफ
लंबाई 8 का एक निर्देशित चक्र ग्राफ
एक निर्देशित चक्र ग्राफ एक चक्र ग्राफ का एक निर्देशित संस्करण है, जिसमें सभी किनारे एक ही दिशा में उन्मुख होते हैं।
एक निर्देशित ग्राफ़ में, किनारों का एक समूह जिसमें प्रत्येक निर्देशित चक्र से कम से कम एक किनारा (या 'आर्क') होता है, को फीडबैक आर्क समूह कहा जाता है। इसी तरह, प्रत्येक निर्देशित चक्र से कम से कम एक शीर्ष वाले वर्टिकल के समूह को फीडबैक शीर्षसमूह कहा जाता है।
एक निर्देशित चक्र ग्राफ़ में एक समान इन-डिग्री 1 और एकसमान आउट-डिग्री 1 होता है।
निर्देशित चक्र ग्राफ चक्रीय समूहों के लिए केली ग्राफ हैं (उदाहरण के लिए ट्रेविसन देखें)।
यह भी देखें
Wikimedia Commons has media related to Cycle graphs.
- पूरा द्विपक्षीय ग्राफ
- पूरा ग्राफ
- सर्कुलेंट ग्राफ
- चक्र ग्राफ (बीजगणित)
- शून्य ग्राफ
- पथ ग्राफ
संदर्भ
- ↑ Some simple graph spectra. win.tue.nl
- ↑ Diestel (2017) p. 8, §1.3
- ↑ "Problem 11707". Amer. Math. Monthly. 120 (5): 469–476. May 2013. doi:10.4169/amer.math.monthly.120.05.469. JSTOR 10.4169/amer.math.monthly.120.05.469. S2CID 41161918.
स्रोत
- Diestel, Reinhard (2017). ग्राफ सिद्धांत (5 ed.). Springer. ISBN 978-3-662-53621-6.
बाहरी संबंध
- Weisstein, Eric W. "Cycle Graph". MathWorld. (discussion of both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams)
- Luca Trevisan, Characters and Expansion।
