चक्र ग्राफ

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 एन का डायहेड्रल समूह। विशेष रूप से, किसी भी शीर्ष को किसी अन्य शीर्ष पर और किसी किनारे को किसी अन्य किनारे पर ले जाने वाली समरूपता मौजूद होती है, इसलिए एन-चक्र एक सममित ग्राफ है।

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

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

लंबाई 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.