साइकिल ग्राफ

From Vigyanwiki
चक्र
Girthn
Automorphisms2n (Dn)
Chromatic number3 यदि n विषम है
2 अन्यथा
Chromatic index3 यदि n विषम है
2 अन्यथा
Spectrum[1]
Properties2-नियमित
शीर्ष-संक्रामक
किनारे-संक्रामक
इकाई दूरी
हैमिल्टनियन
यूलेरियन
NotationCn
Table of graphs and parameters

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

शब्दावली

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

गुण

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

इसके साथ ही:

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

  1. Some simple graph spectra. win.tue.nl
  2. Diestel (2017) p. 8, §1.3
  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.


स्रोत

बाहरी संबंध