साइकिल ग्राफ
चक्र | |
---|---|
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-चक्र एक सममित ग्राफ है।
प्लेटोनिक ग्राफ के समान, चक्र ग्राफ़ डायहेड्रॉन के ढांचे बनाते हैं। उनके दोहरे द्विध्रुव रेखांकन हैं, जो हेड्रॉन पेंट के ढांचे बनाते हैं।
निर्देशित चक्र ग्राफ
निर्देशित चक्र ग्राफ एक चक्र ग्राफ का निर्देशित संस्करण है, जिसमें सभी किनारे एक ही दिशा में उन्मुख होते हैं।
निर्देशित ग्राफ में, किनारों का एक समूह जिसमें प्रत्येक निर्देशित चक्र से कम से कम एक किनारा (या 'वृत्त-चाप') होता है, को प्रतिपुष्टि वृत्त-चाप समूह कहा जाता है। इसी प्रकार, प्रत्येक निर्देशित चक्र से कम से कम एक शीर्ष वाले शीर्ष के समूह को प्रतिपुष्टि शीर्षसमूह कहा जाता है।
निर्देशित चक्र ग्राफ़ में एक समान इन-डिग्री 1 और एकसमान आउट-डिग्री 1 होता है।
निर्देशित चक्र ग्राफ चक्रीय समूहों के लिए केली ग्राफ हैं (उदाहरण के लिए ट्रेविसन देखें)।
यह भी देखें
- पूर्ण द्विपक्षीय ग्राफ
- पूर्ण ग्राफ
- वृत्ताकार ग्राफ
- चक्र ग्राफ(बीजगणित)
- शून्य ग्राफ
- पथ ग्राफ
संदर्भ
- ↑ 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।