साइकिल ग्राफ

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 है; अर्थात्, प्रत्येक शीर्ष के ठीक दो किनारे आपस में जुड़े होते हैं।

शब्दावली

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

गुण

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

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

इसके साथ ही:

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

प्लेटोनिक ग्राफ़ के समान, चक्र ग्राफ़ डायहेड्रॉन के कंकाल बनाते हैं। उनके दोहरे द्विध्रुव रेखांकन हैं, जो 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.