साइकिल ग्राफ

This article is about connected, 2-regular graphs. For other uses, see Cyclic graph.

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	$\left\{2\cos \left({\frac {2k\pi }{n}}\right);k=1,\cdots ,n\right\}$
Properties	2-regular Vertex-transitive Edge-transitive Unit distance Hamiltonian Eulerian
Notation	Cn
Table of graphs and parameters

ग्राफ़ सिद्धांत में, एक चक्र ग्राफ़ या वृत्ताकार ग्राफ़ एक ऐसा ग्राफ़ (असतत गणित) होता है जिसमें एक एकल चक्र (ग्राफ़ सिद्धांत) होता है, या दूसरे शब्दों में, शीर्ष(ग्राफ़ सिद्धांत) की कुछ संख्या (कम से कम 3, यदि ग्राफ़ सरल ग्राफ है) एक बंद श्रृंखला में जुड़ा हुआ है। n शीर्षों वाले चक्र ग्राफ को C_n कहा जाता है। C_n में शीर्षों की संख्या किनारे (ग्राफ सिद्धांत) की संख्या के बराबर है, और प्रत्येक शीर्ष की डिग्री (ग्राफ सिद्धांत) 2 है; अर्थात्, प्रत्येक शीर्ष के ठीक दो किनारे आपस में जुड़े होते हैं।

शब्दावली

चक्र ग्राफ के लिए कई समानार्थक शब्द हैं। इनमें सरल चक्र ग्राफ और चक्रीय ग्राफ सम्मिलित हैं, यद्यपि बाद वाले शब्द का प्रयोग बहुत कम होता है, क्योंकि यह उन ग्राफों को भी संदर्भित कर सकता है जो निर्देशित अचक्रीय ग्राफ को निर्देशित नहीं करते हैं। ग्राफ सिद्धांतकारों में, चक्र, बहुभुज, या n-गॉन भी प्रायः उपयोग किए जाते हैं। 'n'-चक्र शब्द का प्रयोग कभी-कभी अन्य समायोजन में किया जाता है। सम संख्याओं वाले चक्र को सम चक्र कहा जाता है; एक विषम संख्या वाले चक्र को एक विषम चक्र कहा जाता है।

गुण

एक चक्र ग्राफ है:

• के-एज रंगीन|2-एज कलरेबल, अगर और केवल अगर इसमें वर्टिकल की संख्या सम है
• नियमित ग्राफ|2-नियमित
• द्विदलीय ग्राफ|2-शीर्ष रंगीन, यदि और केवल यदि इसमें शीर्षों की संख्या सम है। अधिक आम तौर पर, एक ग्राफ द्विदलीय होता है यदि और केवल यदि इसमें कोई विषम चक्र न हो (डेनेस कोनिग | कोनिग, 1936)।
• जुड़ा हुआ ग्राफ
• यूलेरियन ग्राफ
• हैमिल्टनियन ग्राफ
• एक इकाई दूरी ग्राफ

इसके साथ ही:

• चूंकि चक्र ग्राफ नियमित बहुभुज के रूप में ग्राफ ड्राइंग हो सकते हैं, n-चक्र का ऑटोमोर्फिज्म समूह n पक्षों वाले नियमित बहुभुज के समान होता है, ऑर्डर 2 n के डायहेड्रल समूह। विशेष रूप से, किसी भी शीर्ष को किसी अन्य शीर्ष पर और किसी भी किनारे को किसी भी किनारे पर ले जाने वाली समरूपता मौजूद होती है, इसलिए n-चक्र एक सममित ग्राफ है।

प्लेटोनिक ग्राफ़ के समान, चक्र ग्राफ़ डायहेड्रॉन के कंकाल बनाते हैं। उनके दोहरे द्विध्रुव रेखांकन हैं, जो hosohedron के कंकाल बनाते हैं।

निर्देशित चक्र ग्राफ

लंबाई 8 का एक निर्देशित चक्र ग्राफ

एक निर्देशित चक्र ग्राफ एक चक्र ग्राफ का एक निर्देशित संस्करण है, जिसमें सभी किनारे एक ही दिशा में उन्मुख होते हैं।

एक निर्देशित ग्राफ़ में, किनारों का एक समूह जिसमें प्रत्येक निर्देशित चक्र से कम से कम एक किनारा (या 'आर्क') होता है, को फीडबैक आर्क समूह कहा जाता है। इसी तरह, प्रत्येक निर्देशित चक्र से कम से कम एक शीर्ष वाले वर्टिकल के समूह को फीडबैक शीर्षसमूह कहा जाता है।

एक निर्देशित चक्र ग्राफ़ में एक समान इन-डिग्री 1 और एकसमान आउट-डिग्री 1 होता है।

निर्देशित चक्र ग्राफ चक्रीय समूहों के लिए केली ग्राफ हैं (उदाहरण के लिए ट्रेविसन देखें)।

यह भी देखें

• पूरा द्विपक्षीय ग्राफ
• पूरा ग्राफ
• सर्कुलेंट ग्राफ
• चक्र ग्राफ (बीजगणित)
• शून्य ग्राफ
• पथ ग्राफ

स्रोत

• 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।