साइकिल ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Graph with nodes connected in a closed chain}} | {{Short description|Graph with nodes connected in a closed chain}} | ||
{{About| | {{About|संयोजित, 2-नियमित रेखांकन||चक्रीय ग्राफ}} | ||
{{infobox graph | {{infobox graph | ||
| name = | | name = चक्र | ||
| automorphisms = {{math|2{{mvar|n}}}} ({{mvar|D<sub>n</sub>}}) | | automorphisms = {{math|2{{mvar|n}}}} ({{mvar|D<sub>n</sub>}}) | ||
| chromatic_number = 3 | | chromatic_number = 3 यदि {{mvar|n}} विषम है<br/>2 अन्यथा | ||
| chromatic_index = 3 | | chromatic_index = 3 यदि {{mvar|n}} विषम है<br/>2 अन्यथा | ||
| girth = {{mvar|n}} | | girth = {{mvar|n}} | ||
| spectrum = {{nowrap|<math>\left\{ 2\cos\left(\frac{2k\pi}{n}\right); k=1,\cdots,n \right\}</math><ref>[http://www.win.tue.nl/~aeb/2WF02/easyspectra.pdf Some simple graph spectra]. win.tue.nl</ref>}} | | spectrum = {{nowrap|<math>\left\{ 2\cos\left(\frac{2k\pi}{n}\right); k=1,\cdots,n \right\}</math><ref>[http://www.win.tue.nl/~aeb/2WF02/easyspectra.pdf Some simple graph spectra]. win.tue.nl</ref>}} | ||
| notation = {{mvar|C{{sub|n}}}} | | notation = {{mvar|C{{sub|n}}}} | ||
| properties = [[Regular graph|2- | | properties = [[Regular graph|2-नियमित]]<br>[[Vertex-transitive graph|शीर्ष-संक्रामक]]<br>[[Edge-transitive graph|किनारे-संक्रामक]]<br>[[Unit distance graph|इकाई दूरी]]<br>[[Hamiltonian graph|हैमिल्टनियन]]<br>[[Eulerian graph|यूलेरियन]] | ||
}} | }} | ||
ग्राफ़ सिद्धांत में, | ग्राफ़ सिद्धांत में, चक्र ग्राफ़ या वृत्ताकार ग्राफ़ एक ऐसा ग्राफ़(असतत गणित) होता है जिसमें एकल चक्र(ग्राफ़ सिद्धांत) होता है, या दूसरे शब्दों में, शीर्ष(ग्राफ़ सिद्धांत) की कुछ संख्या(कम से कम 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> सम संख्याओं वाले चक्र को सम चक्र कहा जाता है; एक विषम संख्या वाले चक्र को विषम चक्र कहा जाता है। | ||
== गुण == | == गुण == | ||
एक चक्र ग्राफ है: | एक चक्र ग्राफ है: | ||
* [[के-एज रंगीन|2-एज रंगीन]], [[अगर और केवल अगर|यदि | * [[के-एज रंगीन|2-एज रंगीन]], [[अगर और केवल अगर|यदि और मात्र यदि]] इसमें शीर्ष की संख्या सम है | ||
* [[नियमित ग्राफ]] | * [[नियमित ग्राफ]] | ||
* द्विदलीय ग्राफ, यदि और मात्र यदि इसमें शीर्षों की संख्या सम है। अधिक सामान्यतः , एक ग्राफ द्विदलीय होता है यदि और मात्र यदि इसमें कोई विषम चक्र न हो (डेनेस कोनिग, 1936)। | * द्विदलीय ग्राफ, यदि और मात्र यदि इसमें शीर्षों की संख्या सम है। अधिक सामान्यतः, एक ग्राफ द्विदलीय होता है यदि और मात्र यदि इसमें कोई विषम चक्र न हो(डेनेस कोनिग, 1936)। | ||
* [[जुड़ा हुआ ग्राफ|संयोजित ग्राफ]] | * [[जुड़ा हुआ ग्राफ|संयोजित ग्राफ]] | ||
* [[यूलेरियन ग्राफ]] | * [[यूलेरियन ग्राफ]] | ||
| Line 28: | Line 28: | ||
इसके साथ ही: | इसके साथ ही: | ||
* चूंकि चक्र ग्राफ [[नियमित बहुभुज]] के रूप में [[ग्राफ ड्राइंग|ग्राफ आलेख]] हो सकते हैं, n-चक्र का [[ऑटोमोर्फिज्म समूह]] n पक्षों वाले नियमित बहुभुज के समान होता है, | * चूंकि चक्र ग्राफ [[नियमित बहुभुज]] के रूप में [[ग्राफ ड्राइंग|ग्राफ आलेख]] हो सकते हैं, n-चक्र का [[ऑटोमोर्फिज्म समूह|स्वसमाकृतिकता समूह]] n पक्षों वाले नियमित बहुभुज के समान होता है, क्रम 2n के [[डायहेड्रल समूह|द्वितल समूह]]। विशेष रूप से, किसी भी शीर्ष को किसी अन्य शीर्ष पर और किसी भी किनारे को किसी भी किनारे पर ले जाने वाली समरूपता स्थित होती है, इसलिए n-चक्र एक [[सममित ग्राफ]] है। | ||
[[प्लेटोनिक ग्राफ]] | [[प्लेटोनिक ग्राफ]] के समान, चक्र ग्राफ़ [[डायहेड्रॉन]] के ढांचे बनाते हैं। उनके दोहरे द्विध्रुव रेखांकन हैं, जो [[hosohedron|हेड्रॉन पेंट]] के ढांचे बनाते हैं। | ||
== निर्देशित चक्र ग्राफ == | == निर्देशित चक्र ग्राफ == | ||
[[Image:DC8.png|frame|right|लंबाई 8 का एक निर्देशित चक्र ग्राफ]] | [[Image:DC8.png|frame|right|लंबाई 8 का एक निर्देशित चक्र ग्राफ]]निर्देशित चक्र ग्राफ एक चक्र ग्राफ का निर्देशित संस्करण है, जिसमें सभी किनारे एक ही दिशा में उन्मुख होते हैं। | ||
[[निर्देशित ग्राफ]] में, किनारों का एक समूह जिसमें प्रत्येक निर्देशित चक्र से कम से कम एक किनारा(या 'वृत्त-चाप') होता है, को [[फीडबैक आर्क सेट|प्रतिपुष्टि वृत्त-चाप समूह]] कहा जाता है। इसी प्रकार, प्रत्येक निर्देशित चक्र से कम से कम एक शीर्ष वाले शीर्ष के समूह को [[फीडबैक वर्टेक्स सेट|प्रतिपुष्टि शीर्षसमूह]] कहा जाता है। | |||
निर्देशित चक्र ग्राफ़ में एक समान इन-डिग्री 1 और एकसमान आउट-डिग्री 1 होता है। | |||
निर्देशित चक्र ग्राफ [[चक्रीय समूह]] | निर्देशित चक्र ग्राफ [[चक्रीय समूह|चक्रीय समूहों]] के लिए [[केली ग्राफ]] हैं(उदाहरण के लिए ट्रेविसन देखें)। | ||
== यह भी देखें == | == यह भी देखें == | ||
{{commons category|Cycle graphs}} | {{commons category|Cycle graphs}} | ||
* | * पूर्ण द्विपक्षीय ग्राफ | ||
* [[पूरा ग्राफ]] | * [[पूरा ग्राफ|पूर्ण ग्राफ]] | ||
* [[सर्कुलेंट ग्राफ]] | * [[सर्कुलेंट ग्राफ|वृत्ताकार ग्राफ]] | ||
* [[साइकिल ग्राफ (बीजगणित)|चक्र ग्राफ (बीजगणित)]] | * [[साइकिल ग्राफ (बीजगणित)|चक्र ग्राफ(बीजगणित)]] | ||
* [[शून्य ग्राफ]] | * [[शून्य ग्राफ]] | ||
* [[पथ ग्राफ]] | * [[पथ ग्राफ]] | ||
| Line 58: | Line 58: | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
*{{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 11:03, 26 March 2023
| चक्र | |
|---|---|
| Girth | n |
| Automorphisms | 2n (Dn) |
| Chromatic number | 3 यदि n विषम है 2 अन्यथा |
| Chromatic index | 3 यदि n विषम है 2 अन्यथा |
| Spectrum | [1] |
| Properties | 2-नियमित शीर्ष-संक्रामक किनारे-संक्रामक इकाई दूरी हैमिल्टनियन यूलेरियन |
| Notation | Cn |
| Table of graphs and parameters | |
ग्राफ़ सिद्धांत में, चक्र ग्राफ़ या वृत्ताकार ग्राफ़ एक ऐसा ग्राफ़(असतत गणित) होता है जिसमें एकल चक्र(ग्राफ़ सिद्धांत) होता है, या दूसरे शब्दों में, शीर्ष(ग्राफ़ सिद्धांत) की कुछ संख्या(कम से कम 3, यदि ग्राफ़ सरल ग्राफ है) एक बंद श्रृंखला में जुड़ा हुआ है। n शीर्षों वाले चक्र ग्राफ को Cn कहा जाता है।[2] Cn में शीर्षों की संख्या किनारे(ग्राफ सिद्धांत) की संख्या के बराबर है, और प्रत्येक शीर्ष की डिग्री(ग्राफ सिद्धांत) 2 है; अर्थात्, प्रत्येक शीर्ष के ठीक दो किनारे आपस में जुड़े होते हैं।
शब्दावली
चक्र ग्राफ के लिए कई समानार्थक शब्द हैं। इनमें सरल चक्र ग्राफ और चक्रीय ग्राफ सम्मिलित हैं, यद्यपि बाद वाले शब्द का प्रयोग बहुत कम होता है, क्योंकि यह उन ग्राफों को भी संदर्भित कर सकता है जो निर्देशित अचक्रीय ग्राफ को निर्देशित नहीं करते हैं। ग्राफ सिद्धांतकारों में, चक्र, बहुभुज, या n-गॉन भी प्रायः उपयोग किए जाते हैं। 'n'-चक्र शब्द का प्रयोग कभी-कभी अन्य समायोजन में किया जाता है।[3] सम संख्याओं वाले चक्र को सम चक्र कहा जाता है; एक विषम संख्या वाले चक्र को विषम चक्र कहा जाता है।
गुण
एक चक्र ग्राफ है:
- 2-एज रंगीन, यदि और मात्र यदि इसमें शीर्ष की संख्या सम है
- नियमित ग्राफ
- द्विदलीय ग्राफ, यदि और मात्र यदि इसमें शीर्षों की संख्या सम है। अधिक सामान्यतः, एक ग्राफ द्विदलीय होता है यदि और मात्र यदि इसमें कोई विषम चक्र न हो(डेनेस कोनिग, 1936)।
- संयोजित ग्राफ
- यूलेरियन ग्राफ
- हैमिल्टनियन ग्राफ
- एक इकाई दूरी ग्राफ
इसके साथ ही:
- चूंकि चक्र ग्राफ नियमित बहुभुज के रूप में ग्राफ आलेख हो सकते हैं, n-चक्र का स्वसमाकृतिकता समूह n पक्षों वाले नियमित बहुभुज के समान होता है, क्रम 2n के द्वितल समूह। विशेष रूप से, किसी भी शीर्ष को किसी अन्य शीर्ष पर और किसी भी किनारे को किसी भी किनारे पर ले जाने वाली समरूपता स्थित होती है, इसलिए n-चक्र एक सममित ग्राफ है।
प्लेटोनिक ग्राफ के समान, चक्र ग्राफ़ डायहेड्रॉन के ढांचे बनाते हैं। उनके दोहरे द्विध्रुव रेखांकन हैं, जो हेड्रॉन पेंट के ढांचे बनाते हैं।
निर्देशित चक्र ग्राफ
लंबाई 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।
