चक्र (ग्राफ़ सिद्धांत): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Trail in which only the first and last vertices are equal.}}
{{Short description|Trail in which only the first and last vertices are equal.}}
[[File:Graph cycle.svg|thumb|एक पथ (ग्राफ़ सिद्धांत) को चित्रित करने के लिए किनारों को रंगीन करने वाला एक ग्राफ #वॉक, ट्रेल, और पथ H-A-B-A-H को हरे रंग में, एक सर्किट जो एक बंद वॉक है जिसमें सभी किनारे अलग-अलग हैं B-D-E -F-D-C-B नीले रंग में, और एक चक्र जो एक बंद चाल है जिसमें सभी शीर्ष अलग-अलग हैं लेकिन पहला और अंतिम शीर्ष H-D-G-H लाल रंग में है।]]ग्राफ़ सिद्धांत में, ग्राफ़ (असतत गणित) में एक चक्र एक गैर-रिक्त पथ ([[ग्राफ सिद्धांत]]) #वॉक, ट्रेल और पथ है जिसमें केवल पहला और अंतिम [[वर्टेक्स (ग्राफ़ सिद्धांत)]] बराबर होते हैं। [[निर्देशित ग्राफ]] में एक निर्देशित चक्र एक गैर-रिक्त पथ है (ग्राफ सिद्धांत)#निर्देशित चलना, निर्देशित पथ और निर्देशित पथ जिसमें केवल पहला और अंतिम शीर्ष बराबर होते हैं।
[[File:Graph cycle.svg|thumb|हरे रंग में एक बंद वॉक एच-ए-बी-ए-एच को दर्शाने के लिए किनारों को रंगीन करने वाला एक ग्राफ, एक परिपथ जो एक बंद वॉक है जिसमें सभी किनारे नीले रंग में अलग-अलग बी-डी--एफ-डी-सी-बी हैं , और एक चक्र जो एक बंद चाल है जिसमें सभी शीर्ष अलग-अलग हैं लेकिन पहला और अंतिम शीर्ष एच-डी-जी-एच लाल रंग में है।]]'''ग्राफ़ सिद्धांत''' में, ग्राफ़ (असतत गणित) में एक चक्र एक गैर-रिक्त पथ ([[ग्राफ सिद्धांत]]) या वॉक, ट्रेल और पथ है जिसमें केवल प्रथम  और अंतिम [[वर्टेक्स (ग्राफ़ सिद्धांत)]] समान  होते हैं। [[निर्देशित ग्राफ]] में एक निर्देशित चक्र एक गैर-रिक्त पथ है (ग्राफ सिद्धांत) या निर्देशित चलना, निर्देशित पथ और निर्देशित पथ जिसमें केवल प्रथम  और अंतिम शीर्ष समान  होते हैं।


बिना चक्र वाले ग्राफ को ''एसाइक्लिक ग्राफ'' कहा जाता है। निर्देशित चक्रों के बिना एक निर्देशित ग्राफ को ''[[निर्देशित अचक्रीय ग्राफ]]'' कहा जाता है। चक्रों के बिना जुड़े हुए ग्राफ़ को ''ट्री (ग्राफ़ सिद्धांत)'' कहा जाता है।
इस प्रकार से बिना चक्र वाले ग्राफ को ''एसाइक्लिक ग्राफ'' कहा जाता है। निर्देशित चक्रों के बिना एक निर्देशित ग्राफ को ''[[निर्देशित अचक्रीय ग्राफ]]'' कहा जाता है। और चक्रों के बिना जुड़े हुए ग्राफ़ को ''ट्री (ग्राफ़ सिद्धांत)'' कहा जाता है।


== परिभाषाएँ ==
== परिलैंग्वेज एँ ==


=== सर्किट और चक्र ===
=== परिपथ और चक्र ===
* एक सर्किट एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत)#वॉक, ट्रेल और पथ जिसमें पहला और अंतिम शीर्ष बराबर होते हैं (''बंद ट्रेल'')।{{sfn|Bender|Williamson|2010|p=164}}
* एक परिपथ एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत) या वॉक, ट्रेल और पथ जिसमें प्प्रथम  और अंतिम शीर्ष समान (''बंद ट्रेल'') होते हैं ।{{sfn|Bender|Williamson|2010|p=164}}  
: होने देना {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} एक ग्राफ बनें. सर्किट एक गैर-रिक्त पथ है {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n''</sub>)}} शीर्ष क्रम के साथ {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>, ''v''<sub>1</sub>)}}.
:मान लीजिए {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} एक ग्राफ है। और परिपथ एक शीर्ष अनुक्रम (v1, v2, …, vn, v1) के साथ एक गैर-रिक्त पथ {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n''</sub>)}} है।
*चक्र या सरल परिपथ एक ऐसा परिपथ है जिसमें केवल प्रथम और अंतिम शीर्ष बराबर होते हैं।{{sfn|Bender|Williamson|2010|p=164}}
*चक्र या सरल परिपथ एक ऐसा परिपथ है जिसमें केवल प्रथम और अंतिम शीर्ष समान  होते हैं।{{sfn|Bender|Williamson|2010|p=164}}


=== निर्देशित सर्किट और निर्देशित चक्र ===
=== निर्देशित परिपथ और निर्देशित चक्र ===
* एक निर्देशित सर्किट एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत)#निर्देशित चलना, निर्देशित पथ, और निर्देशित पथ जिसमें पहला और अंतिम शीर्ष बराबर होते हैं (''बंद निर्देशित पथ'')।{{sfn|Bender|Williamson|2010|p=164}}
* एक निर्देशित परिपथ एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत) या निर्देशित चलना, निर्देशित पथ, और निर्देशित पथ जिसमें पहला और अंतिम शीर्ष समान  होते हैं (''बंद निर्देशित पथ'')।{{sfn|Bender|Williamson|2010|p=164}}  
: होने देना {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} एक निर्देशित ग्राफ बनें। एक निर्देशित सर्किट एक गैर-रिक्त निर्देशित पथ है {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n''</sub>)}} शीर्ष क्रम के साथ {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>, ''v''<sub>1</sub>)}}.
मान लीजिए {{nowrap|1=''G'' = (''V'', ''E'', ''ϕ'')}} एक निर्देशित ग्राफ है। एक निर्देशित परिपथ एक शीर्ष अनुक्रम {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>, ''v''<sub>1</sub>)}} के साथ एक गैर-रिक्त निर्देशित पथ {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, …, ''e''<sub>''n''</sub>)}} है।.
* एक निर्देशित चक्र या सरल निर्देशित सर्किट एक निर्देशित सर्किट होता है जिसमें केवल पहला और अंतिम शीर्ष बराबर होता है।{{sfn|Bender|Williamson|2010|p=164}}
* एक निर्देशित चक्र या सरल निर्देशित परिपथ एक निर्देशित परिपथ होता है जिसमें केवल पहला और अंतिम शीर्ष समान  होता है।{{sfn|Bender|Williamson|2010|p=164}}  


== तार रहित चक्र ==
== तार रहित चक्र ==
[[File:Graph with Chordless and Chorded Cycles.svg|thumb|right|इस ग्राफ़ में हरा चक्र A-B-C-D-E-F-A ताररहित है जबकि लाल चक्र G-H-I-J-K-L-G नहीं है। ऐसा इसलिए है क्योंकि किनारा {K, I} एक राग है।]]ग्राफ़ में एक [[ताररहित चक्र]], जिसे छेद या प्रेरित चक्र भी कहा जाता है, एक ऐसा चक्र है जिसमें चक्र के कोई भी दो शीर्ष किसी ऐसे किनारे से नहीं जुड़े होते हैं जो स्वयं चक्र से संबंधित नहीं होता है। एक एंटीहोल एक ग्राफ़ होल का [[पूरक ग्राफ]]है। कॉर्डलेस चक्रों का उपयोग सही ग्राफ़ को चिह्नित करने के लिए किया जा सकता है: मजबूत [[ उत्तम ग्राफ |उत्तम ग्राफ]] प्रमेय के अनुसार, एक ग्राफ़ तभी सही होता है जब उसके किसी भी छेद या एंटीहोल में विषम संख्या में कोने न हों जो तीन से अधिक हो। [[कॉर्डल ग्राफ]], एक विशेष प्रकार का पूर्ण ग्राफ़, जिसमें तीन से अधिक आकार का कोई छेद नहीं होता है।
[[File:Graph with Chordless and Chorded Cycles.svg|thumb|right|इस ग्राफ़ में हरा चक्र -बी-सी-डी--एफ-ताररहित है जबकि लाल चक्र जी-एच-आई-जे-के-एल-जी नहीं है। ऐसा इसलिए है क्योंकि किनारा {के, आई} एक राग है।]]ग्राफ़ में एक [[ताररहित चक्र]], जिसे छिद्र  या प्रेरित चक्र भी कहा जाता है, यह एक ऐसा चक्र है जिसमें चक्र के कोई भी दो शीर्ष किसी ऐसे किनारे से नहीं जुड़े होते हैं जो की स्वयं चक्र से संबंधित नहीं होता है। किन्तु  एंटीहोल एक ग्राफ़ होल का [[पूरक ग्राफ]] है। इस प्रकार से  कॉर्डलेस चक्रों का उपयोग सही ग्राफ़ को चिह्नित करने के लिए किया जा सकता है: जटिल  [[ उत्तम ग्राफ |उत्तम ग्राफ]] प्रमेय के अनुसार, एक ग्राफ़ तभी सही होता है जब उसके किसी भी छिद्र  या एंटीहोल में विषम संख्या में कोने न हों जो तीन से अधिक हो। [[कॉर्डल ग्राफ]], एक विशेष प्रकार का पूर्ण ग्राफ़, जिसमें तीन से अधिक आकार का कोई छिद्र  नहीं होता है।


किसी ग्राफ का घेरा (ग्राफ़ सिद्धांत) उसके सबसे छोटे चक्र की लंबाई है; यह चक्र आवश्यक रूप से तार रहित है। केज (ग्राफ़ सिद्धांत) को डिग्री और परिधि के दिए गए संयोजनों के साथ सबसे छोटे नियमित ग्राफ़ के रूप में परिभाषित किया गया है।
चूंकि किसी ग्राफ का घेरा (ग्राफ़ सिद्धांत) उसके सामान्य  लघु  चक्र की लंबाई है; यह चक्र आवश्यक रूप से तार रहित होते है। जिससे केज (ग्राफ़ सिद्धांत) को डिग्री और परिधि के दिए गए संयोजनों के साथ अधिक  लघु  नियमित ग्राफ़ के रूप में परिभाषित किया गया है।


एक [[परिधीय चक्र]] एक ग्राफ़ में एक चक्र है जिसमें यह गुण होता है कि चक्र पर नहीं होने वाले प्रत्येक दो किनारों को एक पथ से जोड़ा जा सकता है जिसके आंतरिक कोने चक्र से बचते हैं। ऐसे ग्राफ़ में जो किसी चक्र में एक किनारे जोड़कर नहीं बनता है, एक परिधीय चक्र एक प्रेरित चक्र होना चाहिए।
एक [[परिधीय चक्र]] एक ग्राफ़ में एक चक्र है जिसमें यह गुण होता है कि चक्र पर नहीं होने वाले प्रत्येक दो किनारों को एक पथ से जोड़ा जा सकता है जिसके आंतरिक कोने चक्र से बचते हैं। ऐसे ग्राफ़ में जो किसी चक्र में एक किनारे जोड़कर नहीं बनता है, एक परिधीय चक्र एक प्रेरित चक्र होना चाहिए।


== साइकिल स्पेस ==
== चक्र  स्थान  ==
चक्र शब्द ग्राफ़ के [[चक्र स्थान]] के एक तत्व को भी संदर्भित कर सकता है। कई चक्र स्थान हैं, प्रत्येक गुणांक क्षेत्र या रिंग के लिए एक। सबसे आम है बाइनरी साइकल स्पेस (आमतौर पर इसे केवल साइकल स्पेस कहा जाता है), जिसमें किनारे के सेट होते हैं जिनकी प्रत्येक शीर्ष पर डिग्री भी होती है; यह दो-तत्व [[परिमित क्षेत्र]] पर एक [[सदिश स्थल]] बनाता है। वेब्लेन के प्रमेय के अनुसार, चक्र स्थान का प्रत्येक तत्व सरल चक्रों के किनारे-असंबद्ध संघ के रूप में बन सकता है। ग्राफ़ का [[चक्र आधार]] सरल चक्रों का एक सेट है जो चक्र स्थान का [[आधार (रैखिक बीजगणित)]] बनाता है।<ref name="gy">{{citation|title=Graph Theory and Its Applications|edition=2nd|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press|year=2005|isbn=9781584885054|chapter=4.6 Graphs and Vector Spaces|pages=197–207|chapter-url=https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197|access-date=2016-09-27|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204155009/https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197|url-status=live}}.</ref>
इस प्रकार से चक्र शब्द ग्राफ़ के [[चक्र स्थान]] के एक तत्व को भी संदर्भित कर सकता है। और अनेक  चक्र स्थान हैं, प्रत्येक गुणांक क्षेत्र या रिंग के लिए कई चक्र स्थान होते हैं। जो की  अधिक  महत्वपूर्ण होते  है बाइनरी चक्र  स्थान  (सामान्यतः  इसे केवल चक्र  स्थान  कहा जाता है), जिसमें किनारे के समुच्च होते हैं जिनकी प्रत्येक शीर्ष पर डिग्री भी होती है; यह दो-तत्व [[परिमित क्षेत्र]] पर एक [[सदिश स्थल]] बनाता है। वेब्लेन के प्रमेय के अनुसार, चक्र स्थान का प्रत्येक तत्व सरल चक्रों के किनारे-असंबद्ध संघ के रूप में बन सकता है। ग्राफ़ का [[चक्र आधार]] सरल चक्रों का एक समुच्च है जो की चक्र स्थान का [[आधार (रैखिक बीजगणित)]] बनाता है।<ref name="gy">{{citation|title=Graph Theory and Its Applications|edition=2nd|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press|year=2005|isbn=9781584885054|chapter=4.6 Graphs and Vector Spaces|pages=197–207|chapter-url=https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197|access-date=2016-09-27|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204155009/https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197|url-status=live}}.</ref>
[[बीजगणितीय टोपोलॉजी]] के विचारों का उपयोग करते हुए, बाइनरी चक्र स्थान को अन्य रिंग (गणित) जैसे पूर्णांक, तर्कसंगत या वास्तविक संख्याओं आदि पर वेक्टर रिक्त स्थान या [[मॉड्यूल (गणित)]] में सामान्यीकृत किया जाता है।<ref name="diestel">{{citation|title=Graph Theory|volume=173|series=Graduate Texts in Mathematics|first=Reinhard|last=Diestel|publisher=Springer|year=2012|chapter=1.9 Some linear algebra|pages=23–28|chapter-url=https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23|access-date=2016-09-27|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204155010/https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23|url-status=live}}.</ref>


[[बीजगणितीय टोपोलॉजी]] के विचारों का उपयोग करते हुए, बाइनरी चक्र स्थान को अन्य रिंग (गणित) जैसे पूर्णांक, तर्कसंगत या वास्तविक संख्याओं आदि पर सदिश रिक्त स्थान या [[मॉड्यूल (गणित)]] में सामान्यीकृत किया जाता है।<ref name="diestel">{{citation|title=Graph Theory|volume=173|series=Graduate Texts in Mathematics|first=Reinhard|last=Diestel|publisher=Springer|year=2012|chapter=1.9 Some linear algebra|pages=23–28|chapter-url=https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23|access-date=2016-09-27|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204155010/https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23|url-status=live}}.</ref>
== चक्र का पता लगाना ==
निर्देशित और अप्रत्यक्ष ग्राफ़ में एक चक्र का अस्तित्व इस तथ्य  पर निर्धारित किया जा सकता है कि क्या [[गहराई-पहली खोज|गहराई-प्रथम  खोज]] (डीएफएस) को एक किनारा मिलता है जो वर्तमान शीर्ष के पूर्वज को इंगित करता है (इसमें गहराई-प्रथम  खोज या गहराई-प्रथम खोज का आउटपुट सम्मिलित  है).<ref>{{cite book|last=Tucker|first=Alan|author-link=Alan Tucker|title=एप्लाइड कॉम्बिनेटरिक्स|year=2006|publisher=John Wiley & sons|location=Hoboken|isbn=978-0-471-73507-6|edition=5th|page=49|chapter=Chapter 2: Covering Circuits and Graph Colorings}}</ref> इस प्रकार से सभी पिछले किनारे जिन पर डीएफएस छूट जाता है वे चक्रों का भाग होता  हैं।<ref name="sedgewick">{{citation | first=Robert | last=Sedgewick | author-link=Robert Sedgewick (computer scientist) | title=Algorithms | chapter=Graph algorithms | year=1983 | publisher=Addison–Wesley | isbn=0-201-06672-6 | url-access=registration | url=https://archive.org/details/algorithms00sedg }}</ref> एक अप्रत्यक्ष ग्राफ़ में, किसी नोड के पैरेंट के किनारे को पिछले किनारे के रूप में नहीं गिना जाना चाहिए, किन्तु  पहले से देखे गए किसी अन्य शीर्ष को खोजने से  पिछले किनारे का संकेत देता है । अप्रत्यक्ष ग्राफ़ की स्तिथिया  में, एन-वर्टेक्स ग्राफ़ में एक चक्र खोजने के लिए केवल ''O(n)'' समय की आवश्यकता होती है, क्योंकि अधिकतम ''n − 1'' किनारे ट्री  के किनारे हो सकते हैं।


== चक्र का पता लगाना ==
अनेक  [[ टोपोलॉजिकल छँटाई |टोपोलॉजिकल छँटाई]] एल्गोरिदम भी चक्रों का पता लगाएंगे, क्योंकि वे टोपोलॉजिकल ऑर्डर के अस्तित्व में बाधाएं हैं। इसके अतिरिक्त , यदि एक निर्देशित ग्राफ को दृढ़ता से जुड़े घटकों में विभाजित किया गया है, तो चक्र केवल घटकों के अन्दर  उपस्तिथ होते हैं, उनके मध्य उपस्थित  नहीं होते है , क्योंकि चक्र दृढ़ता से जुड़े होते हैं।<ref name="sedgewick" />
निर्देशित और अप्रत्यक्ष ग्राफ़ में एक चक्र का अस्तित्व इस बात से निर्धारित किया जा सकता है कि क्या [[गहराई-पहली खोज]] (डीएफएस) को एक किनारा मिलता है जो वर्तमान शीर्ष के पूर्वज को इंगित करता है (इसमें गहराई-पहली खोज#गहराई-पहली खोज का आउटपुट शामिल है) ).<ref>{{cite book|last=Tucker|first=Alan|author-link=Alan Tucker|title=एप्लाइड कॉम्बिनेटरिक्स|year=2006|publisher=John Wiley & sons|location=Hoboken|isbn=978-0-471-73507-6|edition=5th|page=49|chapter=Chapter 2: Covering Circuits and Graph Colorings}}</ref> सभी पिछले किनारे जिन पर डीएफएस छूट जाता है वे चक्रों का हिस्सा हैं।<ref name="sedgewick">{{citation | first=Robert | last=Sedgewick | author-link=Robert Sedgewick (computer scientist) | title=Algorithms | chapter=Graph algorithms | year=1983 | publisher=Addison–Wesley | isbn=0-201-06672-6 | url-access=registration | url=https://archive.org/details/algorithms00sedg }}</ref> एक अप्रत्यक्ष ग्राफ़ में, किसी नोड के पैरेंट के किनारे को पिछले किनारे के रूप में नहीं गिना जाना चाहिए, लेकिन पहले से देखे गए किसी अन्य शीर्ष को ढूंढना पिछले किनारे का संकेत देगा। अप्रत्यक्ष ग्राफ़ के मामले में, एन-वर्टेक्स ग्राफ़ में एक चक्र खोजने के लिए केवल O(n) समय की आवश्यकता होती है, क्योंकि अधिकतम n − 1 किनारे पेड़ के किनारे हो सकते हैं।


कई [[ टोपोलॉजिकल छँटाई |टोपोलॉजिकल छँटाई]] एल्गोरिदम भी चक्रों का पता लगाएंगे, क्योंकि वे टोपोलॉजिकल ऑर्डर के अस्तित्व में बाधाएं हैं। इसके अलावा, यदि एक निर्देशित ग्राफ को दृढ़ता से जुड़े घटकों में विभाजित किया गया है, तो चक्र केवल घटकों के भीतर मौजूद होते हैं, उनके बीच नहीं, क्योंकि चक्र दृढ़ता से जुड़े होते हैं।<ref name="sedgewick" />
इस प्रकार से निर्देशित ग्राफ़ के लिए, वितरित संदेश-आधारित एल्गोरिदम का उपयोग किया जा सकता है। ये एल्गोरिदम इस विचार पर विश्वाश  करते हैं कि एक चक्र में एक शीर्ष द्वारा भेजा गया संदेश स्वयं वापस आ जाएगा।


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


चक्र पहचान के अनुप्रयोगों में समवर्ती प्रणालियों में [[गतिरोध]] का पता लगाने के लिए [[प्रतीक्षा-ग्राफ़]] का उपयोग शामिल है।<ref>{{cite book
चक्र पहचान के अनुप्रयोगों में समवर्ती प्रणालियों में [[गतिरोध]] का पता लगाने के लिए [[प्रतीक्षा-ग्राफ़|डेडलॉक]] का उपयोग सम्मिलित  है।<ref>{{cite book
   | last = Silberschatz
   | last = Silberschatz
   | first = Abraham
   | first = Abraham
Line 47: Line 47:
   | pages = [https://archive.org/details/operatingsystemc0006silb/page/260 260]
   | pages = [https://archive.org/details/operatingsystemc0006silb/page/260 260]
   | isbn = 0-471-25060-0}}</ref>
   | isbn = 0-471-25060-0}}</ref>
== एल्गोरिथम ==
== एल्गोरिथम ==
<syntaxhighlight>
<syntaxhighlight>
Line 64: Line 62:
     DFS(w)
     DFS(w)
   finished(v) = true
   finished(v) = true
</syntaxhighlight>नेबर का मतलब निर्देशित और अप्रत्यक्ष ग्राफ़ दोनों के लिए v से जुड़े सभी शीर्ष हैं, सिवाय उस शीर्ष को छोड़कर जिसे DFS(v) कहा जाता है। यह एल्गोरिथम को तुच्छ चक्रों को पकड़ने से भी बचाता है, जो कि कम से कम एक किनारे वाले प्रत्येक अप्रत्यक्ष ग्राफ़ में होता है।
</syntaxhighlight>नेबर का मतलब निर्देशित और अप्रत्यक्ष ग्राफ़ दोनों के लिए v से जुड़े सभी शीर्ष हैं, सिवाय उस शीर्ष को छोड़कर जिसे डीएफएस(वी) कहा जाता है। यह एल्गोरिथम को तुच्छ चक्रों को पकड़ने से भी बचाता है, जो कि लघु  से लघु  एक किनारे वाले प्रत्येक अप्रत्यक्ष ग्राफ़ में होता है।


== प्रोग्रामिंग ==
== प्रोग्रामिंग ==
[[प्रोग्रामिंग भाषा]] C_Sharp_(प्रोग्रामिंग_भाषा)|C# में निम्नलिखित उदाहरण एडजेंसी सूचियों का उपयोग करके एक अप्रत्यक्ष ग्राफ़ के एक कार्यान्वयन को दर्शाता है। अप्रत्यक्ष ग्राफ़ को Class_(computer_programming) UndirectedGraph के रूप में घोषित किया गया है। प्रोग्राम को निष्पादित करने में मुख्य विधि_(कंप्यूटर_प्रोग्रामिंग) का उपयोग किया जाता है, जो - यदि कोई मौजूद है - कंसोल पर सबसे छोटा, गैर-तुच्छ चक्र प्रिंट करता है।<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/ Shortest cycle in an undirected unweighted graph] {{Webarchive|url=https://web.archive.org/web/20220111220148/https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/ |date=2022-01-11 }}</ref><syntaxhighlight>
[[प्रोग्रामिंग भाषा|प्रोग्रामिंग लैंग्वेज]] सी_शार्प_(प्रोग्रामिंग_लैंग्वेज ) सी# में निम्नलिखित उदाहरण एडजेंसी सूचियों का उपयोग करके एक अप्रत्यक्ष ग्राफ़ के एक कार्यान्वयन को दर्शाता है। अप्रत्यक्ष ग्राफ़ को क्लास_(कंप्यूटर_प्रोग्रामिंग) अनडायरेक्टेडग्राफ के रूप में घोषित किया गया है। प्रोग्राम को निष्पादित करने में मुख्य विधि_(कंप्यूटर_प्रोग्रामिंग) का उपयोग किया जाता है, जो - यदि कोई उपस्तिथ है - कंसोल पर सबसे छोटा, गैर-तुच्छ चक्र प्रिंट करता है।<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/ Shortest cycle in an undirected unweighted graph] {{Webarchive|url=https://web.archive.org/web/20220111220148/https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/ |date=2022-01-11 }}</ref><syntaxhighlight>
using System;                                                                                            
using System;                                                                                                                                                                                        
using System.Collections.Generic;                                                                          
using System.Collections.Generic;                                                                                                                                                                                                                                        
                                                                                                             
                                                                                                                                                                                                                                                                                                                                     
// Declares the class for the vertices of the graph                                                        
// Declares the class for the vertices of the graph                                                                                                                                                    
class Node                                                                                              
class Node                                                                                                                                                                                                                                                                                                                                                                  
{                                                                                              
{                                                                                                                                                                                                                                                                                                                                      
public int index;                                                                              
public int index;                                                                                                                                                        
public string value;                                                                              
public string value;                                                                                                                                                                    
public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Set of neighbour vertices                
public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Set of neighbour vertices                                                
}                                                                                                            
}                                                                                                                                                                                                                            
                                                                                                             
                                                                                                                                                                                 
// Declares the class for the undirected graph
// Declares the class for the undirected graph                                                        
class UndirectedGraph                                                                                        
class UndirectedGraph                                                                                                                                      
{                                                                                                    
{                                                                                                                                                                                                                  
public HashSet<Node> nodes = new HashSet<Node>();                                                  
public HashSet<Node> nodes = new HashSet<Node>();                                                                                                      
                                                                                                 
                                                                                                                                                                                                           
// This method connects node1 and node2 with each other                                        
// This method connects node1 and node2 with each other                                                                                      
public void ConnectNodes(Node node1, Node node2)                                                    
public void ConnectNodes(Node node1, Node node2)                                                                                                          
{
{                                                                                              
node1.adjacentNodes.Add(node2);                                                  
node1.adjacentNodes.Add(node2);                                                                                              
node2.adjacentNodes.Add(node1);                                                            
node2.adjacentNodes.Add(node1);                                                                                                                          
}                                                                                            
}                                                                                                                                                                                          
}                                                                                                        
}                                                                                                                                                                                                                  
 
                                                                                                           
class Program                                                                                  
class Program                                                                                                                                                                  
{
{                                                                                                      
// This method returns the cycle in the form A, B, C, ... as text.                                  
// This method returns the cycle in the form A, B, C, ... as text.                                                                        
public static string ToString(List<Node> cycle)                                                    
public static string ToString(List<Node> cycle)                                                                                            
{                                                                                                
{                                                                                                                                                                                          
string text = "";
string text = "";                                                                      
for (int i = 0; i < cycle.Count; i++) // for-loop, iterating the vertices                       
for (int i = 0; i < cycle.Count; i++) // for-loop, iterating the vertices                       
{  
{                                                                                      
text += cycle[i].value + ", ";                                                  
text += cycle[i].value + ", ";                                                                                                            
}
}                                                                                        
text = text.Substring(0, text.Length - 2);                                              
text = text.Substring(0, text.Length - 2);                                                                                                
return text;                                                                              
return text;                                                                                                                                                          
}                                                                                                
}                                                                                                                                            
                                               
// Main method executing the program                                                              
// Main method executing the program                                                                                                      
public static void Main(string[] args)                                                            
public static void Main(string[] args)                                                                                                        
{                                                                                            
{                                                                                                                                
// Declares and initialises 5 vertices                                             
Node node1 = new Node{index = 0, value = "A"};                                                                                      
Node node1 = new Node{index = 0, value = "A"};                                          
Node node2 = new Node{index = 1, value = "B"};                                                                                    
Node node2 = new Node{index = 1, value = "B"};                                            
Node node3 = new Node{index = 2, value = "C"};                                                                                        
Node node3 = new Node{index = 2, value = "C"};                                          
Node node4 = new Node{index = 3, value = "D"};                                                                                  
Node node4 = new Node{index = 3, value = "D"};                                            
// Declares and initialises an array holding the vertices                                     
// Declares and initialises an array holding the vertices                                     
Node[] nodes = {node1, node2, node3, node4};                                               
Node[] nodes = {node1, node2, node3, node4};                                               
// Creates an undirected graph                            
// Creates an undirected graph                                                              
UndirectedGraph undirectedGraph = new UndirectedGraph();
UndirectedGraph undirectedGraph = new UndirectedGraph();
int numberOfNodes = nodes.Length;
int numberOfNodes = nodes.Length;                                  
for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices
for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices
{                                                                                      
{                                                                                                                                                                              
undirectedGraph.nodes.Add(nodes[i]); // Adds the vertices to the graph
undirectedGraph.nodes.Add(nodes[i]); // Adds the vertices to the graph
}                                                                                        
}                                                                                                                                                          
// Connects the vertices of the graph with each other
// Connects the vertices of the graph with each other
undirectedGraph.ConnectNodes(node1, node1);                                              
undirectedGraph.ConnectNodes(node1, node1);                                                                                            
undirectedGraph.ConnectNodes(node1, node2);
undirectedGraph.ConnectNodes(node1, node2);                                                
undirectedGraph.ConnectNodes(node2, node3);
undirectedGraph.ConnectNodes(node2, node3);                                                  
undirectedGraph.ConnectNodes(node3, node1);
undirectedGraph.ConnectNodes(node3, node1);                                        
undirectedGraph.ConnectNodes(node3, node4);
undirectedGraph.ConnectNodes(node3, node4);                                                  
undirectedGraph.ConnectNodes(node4, node1);
undirectedGraph.ConnectNodes(node4, node1);                                                  
                                                                                       
                                                                                                                                                                                       
HashSet<Node> newNodes = new HashSet<Node>(nodes); // Set of new vertices to iterate
HashSet<Node> newNodes = new HashSet<Node>(nodes); // Set of new vertices to iterate
HashSet<List<Node>> paths = new HashSet<List<Node>>(); // Set of current paths
HashSet<List<Node>> paths = new HashSet<List<Node>>(); // Set of current paths
for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices of the graph
for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices of the graph
{                                                                                        
{                                                                                                                                                                          
Node node = nodes[i];
Node node = nodes[i];
newNodes.Add(node); // Add the vertex to the set of new vertices to iterate
newNodes.Add(node); // Add the vertex to the set of new vertices to iterate
Line 140: Line 137:
path.Add(node);                                                                     
path.Add(node);                                                                     
paths.Add(path); // Adds a path for each node as a starting vertex
paths.Add(path); // Adds a path for each node as a starting vertex
}                                                                                        
}                                                                                                                                                                                        
HashSet<List<Node>> shortestCycles = new HashSet<List<Node>>(); // Set of shortest cycles
HashSet<List<Node>> shortestCycles = new HashSet<List<Node>>(); // Set of shortest cycles
int lengthOfCycles = 0; // Length of shortest cycles
int lengthOfCycles = 0; // Length of shortest cycles
bool cyclesAreFound = false; // Whether or not cycles were found at all
bool cyclesAreFound = false; // Whether or not cycles were found at all
while (!cyclesAreFound && newNodes.Count > 0) // As long as we still had vertices to iterate
while (!cyclesAreFound && newNodes.Count > 0) // As long as we still had vertices to iterate                                                                                                      
{
{                                                                                        
newNodes.Clear(); // Empties the set of nodes to iterate
newNodes.Clear(); // Empties the set of nodes to iterate
HashSet<List<Node>> newPaths = new HashSet<List<Node>>(); // Set of newly found paths
HashSet<List<Node>> newPaths = new HashSet<List<Node>>(); // Set of newly found paths                                                
foreach (List<Node> path in paths) // foreach-loop, iterating all current paths
foreach (List<Node> path in paths) // foreach-loop, iterating all current paths
{
{                                                          
Node lastNode = path[path.Count - 1];
Node lastNode = path[path.Count - 1];
newNodes.Add(lastNode); // Adds the final vertex of the path to the list of vertices to iterate
newNodes.Add(lastNode); // Adds the final vertex of the path to the list of vertices to iterate                                                                                          
foreach (Node nextNode in lastNode.adjacentNodes) // foreach-loop, iterating all neighbours of the previous node
foreach (Node nextNode in lastNode.adjacentNodes) // foreach-loop, iterating all neighbours of the previous node
{
{
if (path.Count >= 3 && path[0] == nextNode) // If a cycle with length greater or equal 3 was found
if (path.Count >= 3 && path[0] == nextNode) // If a cycle with length greater or equal 3 was found
{
{                                                      
cyclesAreFound = true;
cyclesAreFound = true;
shortestCycles.Add(path); // Adds the path to the set of cycles
shortestCycles.Add(path); // Adds the path to the set of cycles                                                                                              
lengthOfCycles = path.Count;
lengthOfCycles = path.Count;
}
}                                                
if (!path.Contains(nextNode)) // If the path doesn't contain the neighbour
if (!path.Contains(nextNode)) // If the path doesn't contain the neighbour                                                            
{
{
newNodes.Add(nextNode); // Adds the neighbour to the set of vertices to iterate
newNodes.Add(nextNode); // Adds the neighbour to the set of vertices to iterate                                                                                  
// Creates a new path
// Creates a new path
List<Node> newPath = new List<Node>();
List<Node> newPath = new List<Node>();
newPath.AddRange(path); // Adds the current path's vertex to the new path in the correct order
newPath.AddRange(path); // Adds the current path's vertex to the new path in the correct order                                                                    
newPath.Add(nextNode); // Adds the neighbour to the new path
newPath.Add(nextNode); // Adds the neighbour to the new path                                                                
newPaths.Add(newPath); // Adds the path to the set of newly found paths
newPaths.Add(newPath); // Adds the path to the set of newly found paths                                                                  
}
}                                  
}
}                                                                            
}
}                                                                                  
paths = newPaths; // Updates the set of current paths
paths = newPaths; // Updates the set of current paths
}
}                                                              
if (shortestCycles.Count > 0) // If cycles were found
if (shortestCycles.Count > 0) // If cycles were found
{
{                                                                              
Console.WriteLine("The graph contains " + shortestCycles.Count + " cycles of length " + lengthOfCycles + "."); // Print to console
Console.WriteLine("The graph contains " + shortestCycles.Count + " cycles of length " + lengthOfCycles + "."); // Print to console
foreach (List<Node> cycle in shortestCycles) // foreach-loop, iterating all found cycles
foreach (List<Node> cycle in shortestCycles) // foreach-loop, iterating all found cycles                                                                  
{
{                                                                  
Console.WriteLine(ToString(cycle)); // Print to console
Console.WriteLine(ToString(cycle)); // Print to console
}
}                                    
}
}                                                                                        
else
else                                                                                  
{
{                                                                                          
Console.WriteLine("The graph contains no cycles."); // Print to console
Console.WriteLine("The graph contains no cycles."); // Print to console
}
}                                                                                            
Console.ReadLine();
Console.ReadLine();                                                                        
}
}                                                                                            
}
}                                                                                                      
</syntaxhighlight>
</syntaxhighlight>


== चक्र द्वारा ग्राफ़ को कवर करना ==
== चक्र द्वारा ग्राफ़ को कवर करना ==
कोनिग्सबर्ग के सात पुलों पर अपने 1736 के पेपर में, जिसे व्यापक रूप से ग्राफ सिद्धांत का जन्म माना जाता है, [[लियोनहार्ड यूलर]] ने साबित किया कि, एक सीमित अप्रत्यक्ष ग्राफ के लिए एक बंद चाल होती है जो प्रत्येक किनारे पर बिल्कुल एक बार जाती है (इसे एक बंद निशान बनाती है), यह आवश्यक और पर्याप्त है कि यह अलग-अलग शीर्षों को छोड़कर जुड़ा हो (अर्थात, सभी किनारे एक घटक में समाहित हों) और प्रत्येक शीर्ष पर सम डिग्री हो। एक निर्देशित ग्राफ़ में प्रत्येक किनारे पर ठीक एक बार जाने वाले बंद वॉक के अस्तित्व के लिए संबंधित लक्षण वर्णन यह है कि ग्राफ़ दृढ़ता से जुड़ा हुआ है और प्रत्येक शीर्ष पर आने वाले और बाहर जाने वाले किनारों की समान संख्या है। किसी भी स्थिति में, परिणामी बंद पथ को [[यूलेरियन पथ]] के रूप में जाना जाता है। यदि एक परिमित अप्रत्यक्ष ग्राफ के प्रत्येक शीर्ष पर सम डिग्री है, चाहे वह जुड़ा हुआ हो या नहीं, तो सरल चक्रों का एक सेट ढूंढना संभव है जो एक साथ प्रत्येक किनारे को बिल्कुल एक बार कवर करते हैं: यह वेब्लेन का प्रमेय है।<ref>{{Citation | last1=Veblen | first1=Oswald | author1-link=Oswald Veblen | title=An Application of Modular Equations in Analysis Situs | jstor=1967604 | series=Second Series | year=1912 | journal=[[Annals of Mathematics]] | volume=14 | issue=1 | pages=86–94 | doi = 10.2307/1967604 }}.</ref> जब एक कनेक्टेड ग्राफ यूलर के प्रमेय की शर्तों को पूरा नहीं करता है, तो [[मार्ग निरीक्षण समस्या]] को हल करके प्रत्येक किनारे को कम से कम एक बार कवर करने वाली न्यूनतम लंबाई का एक बंद चलना बहुपद समय में पाया जा सकता है।
इस प्रकार से कोनिग्सबर्ग के सात पुलों पर अपने 1736 के पेपर में, जिसे व्यापक रूप से ग्राफ सिद्धांत का उत्पत्ति माना जाता है, [[लियोनहार्ड यूलर]] ने प्रमाणित  किया कि, एक सीमित अप्रत्यक्ष ग्राफ के लिए एक बंद चाल होती है जो प्रत्येक किनारे पर पूर्ण रूप से जाती है (इसे बंद चिह्न बनाती है), यह आवश्यक और पर्याप्त है कि यह अलग-अलग शीर्षों को छोड़कर जुड़ा हो (अर्थात, सभी किनारे एक घटक में समाहित हों) और प्रत्येक शीर्ष पर सम डिग्री होती है । किन्तु  निर्देशित ग्राफ़ में प्रत्येक किनारे पर पूर्ण रूप  से  जाने वाले बंद वॉक के अस्तित्व के लिए संबंधित लक्षण वर्णन यह है कि ग्राफ़ दृढ़ता से जुड़ा हुआ है और प्रत्येक शीर्ष पर आने वाले और बाहर जाने वाले किनारों की समान संख्या है। किसी भी स्थिति में, परिणामी बंद पथ को [[यूलेरियन पथ]] के रूप में जाना जाता है। यदि एक परिमित अप्रत्यक्ष ग्राफ के प्रत्येक शीर्ष पर सम डिग्री है, चाहे वह जुड़ा हुआ हो या नहीं, तो सरल चक्रों का एक समुच्च खोजना  संभव है जो एक साथ प्रत्येक किनारे को पूर्ण रूप से  एक बार कवर करते हैं: यह वेब्लेन का प्रमेय है।<ref>{{Citation | last1=Veblen | first1=Oswald | author1-link=Oswald Veblen | title=An Application of Modular Equations in Analysis Situs | jstor=1967604 | series=Second Series | year=1912 | journal=[[Annals of Mathematics]] | volume=14 | issue=1 | pages=86–94 | doi = 10.2307/1967604 }}.</ref> जब एक कनेक्टेड ग्राफ यूलर के प्रमेय की नियम  को पूर्ण  नहीं करता है, तो [[मार्ग निरीक्षण समस्या]] को हल करके प्रत्येक किनारे को पूर्ण रूप से कवर करने वाली न्यूनतम लंबाई का एक बंद चलना बहुपद समय में पाया जा सकता है।


एक एकल सरल चक्र खोजने की समस्या जो किनारों को कवर करने के बजाय प्रत्येक शीर्ष को ठीक एक बार कवर करती है, बहुत कठिन है। ऐसे चक्र को [[हैमिल्टनियन चक्र]] के रूप में जाना जाता है, और यह निर्धारित करना कि यह अस्तित्व में है या नहीं, एनपी-पूर्ण है।<ref>{{citation
किन्तु  एकल सरल चक्र खोजने की समस्या जो किनारों को कवर करने के अतिरिक्त  प्रत्येक शीर्ष को पूर्ण रूप  से  कवर करती है, अधिक  जटिल होते  है। ऐसे चक्र को [[हैमिल्टनियन चक्र]] के रूप में जाना जाता है, और यह निर्धारित करना कि यह अस्तित्व में है या नहीं, एनपी-पूर्ण है।<ref>{{citation
  | author = Richard M. Karp
  | author = Richard M. Karp
  | author-link = Richard M. Karp
  | author-link = Richard M. Karp
Line 208: Line 205:
  | archive-url = https://web.archive.org/web/20210210182452/http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
  | archive-url = https://web.archive.org/web/20210210182452/http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
  | url-status = live
  | url-status = live
  }}.</ref> ग्राफ़ के उन वर्गों के संबंध में बहुत से शोध प्रकाशित किए गए हैं जिनमें हैमिल्टनियन चक्र शामिल होने की गारंटी दी जा सकती है; एक उदाहरण ओरे का प्रमेय है कि एक हैमिल्टनियन चक्र हमेशा एक ग्राफ़ में पाया जा सकता है जिसके लिए प्रत्येक गैर-आसन्न युग्म शीर्षों की डिग्री ग्राफ़ में कम से कम शीर्षों की कुल संख्या के बराबर होती है।<ref>{{citation|first=Ø.|last=Ore|author-link=Øystein Ore|title=Note on Hamilton circuits|journal=[[American Mathematical Monthly]]|volume=67|year=1960|page=55|issue=1|jstor=2308928|doi=10.2307/2308928}}.</ref>
  }}.</ref> ग्राफ़ के उन वर्गों के संबंध में अधिक  शोध प्रकाशित किए गए हैं जिनमें हैमिल्टनियन चक्र सम्मिलित  होने की प्रमाण दिया  जा सकती है; इस प्रकार से  उदाहरण ओरे का प्रमेय है कि एक हैमिल्टनियन चक्र सदैव  एक ग्राफ़ में पाया जा सकता है जिसके लिए प्रत्येक गैर-आसन्न युग्म शीर्षों की डिग्री ग्राफ़ में कम से कम शीर्षों की कुल संख्या के समान  होती है।<ref>{{citation|first=Ø.|last=Ore|author-link=Øystein Ore|title=Note on Hamilton circuits|journal=[[American Mathematical Monthly]]|volume=67|year=1960|page=55|issue=1|jstor=2308928|doi=10.2307/2308928}}.</ref>
[[चक्र डबल कवर अनुमान]] बताता है कि, प्रत्येक [[ब्रिजलेस ग्राफ]]के लिए, सरल चक्रों का एक समूह मौजूद होता है जो ग्राफ़ के प्रत्येक किनारे को ठीक दो बार कवर करता है। यह साबित करना कि यह सत्य है (या इसका प्रति उदाहरण ढूंढना) एक खुली समस्या बनी हुई है।<ref>{{citation
 
अतः [[चक्र डबल कवर अनुमान]] बताता है कि, प्रत्येक [[ब्रिजलेस ग्राफ]] के लिए, सरल चक्रों का एक समूह उपस्तिथ होता है जो ग्राफ़ के प्रत्येक किनारे को ठीक दो बार कवर करता है। यह प्रमाणित  करना कि यह सत्य है (या इसका प्रति उदाहरण खोजना ) जो की एक समस्या बनी हुई है।<ref>{{citation
  | last = Jaeger | first = F.
  | last = Jaeger | first = F.
  | contribution = A survey of the cycle double cover conjecture
  | contribution = A survey of the cycle double cover conjecture
Line 218: Line 216:
  | volume = 27
  | volume = 27
  | year = 1985}}.</ref>
  | year = 1985}}.</ref>
== चक्र द्वारा परिभाषित ग्राफ वर्ग ==
== चक्र द्वारा परिभाषित ग्राफ वर्ग ==
ग्राफ़ के कई महत्वपूर्ण वर्गों को उनके चक्रों द्वारा परिभाषित या चित्रित किया जा सकता है। इसमे शामिल है:
ग्राफ़ के कई महत्वपूर्ण वर्गों को उनके चक्रों द्वारा परिभाषित या चित्रित किया जा सकता है। इसमे सम्मिलित  है:
* [[द्विदलीय ग्राफ]], विषम चक्रों के बिना एक ग्राफ (विषम संख्या में शीर्षों वाला चक्र)
* [[द्विदलीय ग्राफ]], विषम चक्रों के बिना एक ग्राफ (विषम संख्या में शीर्षों वाला चक्र)
* [[कैक्टस ग्राफ]], एक ग्राफ़ जिसमें प्रत्येक गैर-तुच्छ द्विसंबद्ध घटक एक चक्र है
* [[कैक्टस ग्राफ]], एक ग्राफ़ जिसमें प्रत्येक गैर-तुच्छ द्विसंबद्ध घटक एक चक्र है
* [[ चक्र ग्राफ ]], एक ग्राफ़ जिसमें एक चक्र होता है
* [[ चक्र ग्राफ ]], एक ग्राफ़ जिसमें एक चक्र होता है।
* कॉर्डल ग्राफ, एक ग्राफ जिसमें प्रत्येक प्रेरित चक्र एक त्रिकोण है
* कॉर्डल ग्राफ, एक ग्राफ जिसमें प्रत्येक प्रेरित चक्र एक त्रिकोण है।
* निर्देशित चक्रीय ग्राफ, एक निर्देशित ग्राफ जिसमें कोई निर्देशित चक्र नहीं है
* निर्देशित चक्रीय ग्राफ, एक निर्देशित ग्राफ जिसमें कोई निर्देशित चक्र नहीं है।
* रेखा पूर्ण ग्राफ, एक ऐसा ग्राफ जिसमें प्रत्येक विषम चक्र एक त्रिभुज होता है
* रेखा पूर्ण ग्राफ, एक ऐसा ग्राफ जिसमें प्रत्येक विषम चक्र एक त्रिभुज होता है।
[[रेखा पूर्ण ग्राफ़]], एक ऐसा ग्राफ जिसमें कोई प्रेरित चक्र या तीन से अधिक विषम लंबाई के उनके पूरक नहीं हैं
[[रेखा पूर्ण ग्राफ़]], एक ऐसा ग्राफ जिसमें कोई प्रेरित चक्र या तीन से अधिक विषम लंबाई के उनके पूरक नहीं हैं।
* [[छद्मवन]], एक ग्राफ़ जिसमें प्रत्येक जुड़े घटक में अधिकतम एक चक्र होता है
* [[छद्मवन]], एक ग्राफ़ जिसमें प्रत्येक जुड़े घटक में अधिकतम एक चक्र होता है।
* [[गला घोंट दिया गया ग्राफ]], एक ग्राफ़ जिसमें प्रत्येक परिधीय चक्र एक त्रिकोण है
* [[गला घोंट दिया गया ग्राफ|स्ट्रेगुलेटेड   ग्राफ]], एक ग्राफ़ जिसमें प्रत्येक परिधीय चक्र एक त्रिकोण है।
* [[मजबूती से जुड़ा ग्राफ]], एक निर्देशित ग्राफ जिसमें हर किनारा एक चक्र का हिस्सा है
* [[मजबूती से जुड़ा ग्राफ|जटिलता  से जुड़ा ग्राफ]], एक निर्देशित ग्राफ जिसमें हर किनारा एक चक्र का भाग  है।
* त्रिभुज-मुक्त ग्राफ़, तीन-शीर्ष चक्रों के बिना एक ग्राफ़
* त्रिभुज-रहित ग्राफ़, तीन-शीर्ष चक्रों के बिना एक ग्राफ़ है।
* सम-चक्र-मुक्त ग्राफ, सम चक्रों के बिना एक ग्राफ
* सम-चक्र-फ्री ग्राफ, सम चक्रों के बिना एक ग्राफ है।
* सम-छिद्र-रहित ग्राफ़, 6 से बड़ी या उसके बराबर लंबाई वाला सम-चक्र रहित ग्राफ़
* सम-छिद्र-फ्री  ग्राफ़, 6 से उच्च  या उसके समान  लंबाई वाला सम-चक्र रहित ग्राफ़ है।


== यह भी देखें ==
== यह भी देखें ==
* साइकिल स्पेस
* चक्र  स्थान
*चक्र आधार
*चक्र आधार
* पुनरावृत्त फ़ंक्शन मानों के अनुक्रम में [[चक्र का पता लगाना]]
* पुनरावृत्त फ़ंक्शन मानों के अनुक्रम में [[चक्र का पता लगाना]]

Revision as of 16:57, 16 July 2023

हरे रंग में एक बंद वॉक एच-ए-बी-ए-एच को दर्शाने के लिए किनारों को रंगीन करने वाला एक ग्राफ, एक परिपथ जो एक बंद वॉक है जिसमें सभी किनारे नीले रंग में अलग-अलग बी-डी-ई-एफ-डी-सी-बी हैं , और एक चक्र जो एक बंद चाल है जिसमें सभी शीर्ष अलग-अलग हैं लेकिन पहला और अंतिम शीर्ष एच-डी-जी-एच लाल रंग में है।

ग्राफ़ सिद्धांत में, ग्राफ़ (असतत गणित) में एक चक्र एक गैर-रिक्त पथ (ग्राफ सिद्धांत) या वॉक, ट्रेल और पथ है जिसमें केवल प्रथम और अंतिम वर्टेक्स (ग्राफ़ सिद्धांत) समान होते हैं। निर्देशित ग्राफ में एक निर्देशित चक्र एक गैर-रिक्त पथ है (ग्राफ सिद्धांत) या निर्देशित चलना, निर्देशित पथ और निर्देशित पथ जिसमें केवल प्रथम और अंतिम शीर्ष समान होते हैं।

इस प्रकार से बिना चक्र वाले ग्राफ को एसाइक्लिक ग्राफ कहा जाता है। निर्देशित चक्रों के बिना एक निर्देशित ग्राफ को निर्देशित अचक्रीय ग्राफ कहा जाता है। और चक्रों के बिना जुड़े हुए ग्राफ़ को ट्री (ग्राफ़ सिद्धांत) कहा जाता है।

परिलैंग्वेज एँ

परिपथ और चक्र

  • एक परिपथ एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत) या वॉक, ट्रेल और पथ जिसमें प्प्रथम और अंतिम शीर्ष समान (बंद ट्रेल) होते हैं ।[1]
मान लीजिए G = (V, E, ϕ) एक ग्राफ है। और परिपथ एक शीर्ष अनुक्रम (v1, v2, …, vn, v1) के साथ एक गैर-रिक्त पथ (e1, e2, …, en) है।
  • चक्र या सरल परिपथ एक ऐसा परिपथ है जिसमें केवल प्रथम और अंतिम शीर्ष समान होते हैं।[1]

निर्देशित परिपथ और निर्देशित चक्र

  • एक निर्देशित परिपथ एक गैर-रिक्त पथ है (ग्राफ़ सिद्धांत) या निर्देशित चलना, निर्देशित पथ, और निर्देशित पथ जिसमें पहला और अंतिम शीर्ष समान होते हैं (बंद निर्देशित पथ)।[1]

मान लीजिए G = (V, E, ϕ) एक निर्देशित ग्राफ है। एक निर्देशित परिपथ एक शीर्ष अनुक्रम (v1, v2, …, vn, v1) के साथ एक गैर-रिक्त निर्देशित पथ (e1, e2, …, en) है।.

  • एक निर्देशित चक्र या सरल निर्देशित परिपथ एक निर्देशित परिपथ होता है जिसमें केवल पहला और अंतिम शीर्ष समान होता है।[1]

तार रहित चक्र

इस ग्राफ़ में हरा चक्र ए-बी-सी-डी-ई-एफ-ए ताररहित है जबकि लाल चक्र जी-एच-आई-जे-के-एल-जी नहीं है। ऐसा इसलिए है क्योंकि किनारा {के, आई} एक राग है।

ग्राफ़ में एक ताररहित चक्र, जिसे छिद्र या प्रेरित चक्र भी कहा जाता है, यह एक ऐसा चक्र है जिसमें चक्र के कोई भी दो शीर्ष किसी ऐसे किनारे से नहीं जुड़े होते हैं जो की स्वयं चक्र से संबंधित नहीं होता है। किन्तु एंटीहोल एक ग्राफ़ होल का पूरक ग्राफ है। इस प्रकार से कॉर्डलेस चक्रों का उपयोग सही ग्राफ़ को चिह्नित करने के लिए किया जा सकता है: जटिल उत्तम ग्राफ प्रमेय के अनुसार, एक ग्राफ़ तभी सही होता है जब उसके किसी भी छिद्र या एंटीहोल में विषम संख्या में कोने न हों जो तीन से अधिक हो। कॉर्डल ग्राफ, एक विशेष प्रकार का पूर्ण ग्राफ़, जिसमें तीन से अधिक आकार का कोई छिद्र नहीं होता है।

चूंकि किसी ग्राफ का घेरा (ग्राफ़ सिद्धांत) उसके सामान्य लघु चक्र की लंबाई है; यह चक्र आवश्यक रूप से तार रहित होते है। जिससे केज (ग्राफ़ सिद्धांत) को डिग्री और परिधि के दिए गए संयोजनों के साथ अधिक लघु नियमित ग्राफ़ के रूप में परिभाषित किया गया है।

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

चक्र स्थान

इस प्रकार से चक्र शब्द ग्राफ़ के चक्र स्थान के एक तत्व को भी संदर्भित कर सकता है। और अनेक चक्र स्थान हैं, प्रत्येक गुणांक क्षेत्र या रिंग के लिए कई चक्र स्थान होते हैं। जो की अधिक महत्वपूर्ण होते है बाइनरी चक्र स्थान (सामान्यतः इसे केवल चक्र स्थान कहा जाता है), जिसमें किनारे के समुच्च होते हैं जिनकी प्रत्येक शीर्ष पर डिग्री भी होती है; यह दो-तत्व परिमित क्षेत्र पर एक सदिश स्थल बनाता है। वेब्लेन के प्रमेय के अनुसार, चक्र स्थान का प्रत्येक तत्व सरल चक्रों के किनारे-असंबद्ध संघ के रूप में बन सकता है। ग्राफ़ का चक्र आधार सरल चक्रों का एक समुच्च है जो की चक्र स्थान का आधार (रैखिक बीजगणित) बनाता है।[2]

बीजगणितीय टोपोलॉजी के विचारों का उपयोग करते हुए, बाइनरी चक्र स्थान को अन्य रिंग (गणित) जैसे पूर्णांक, तर्कसंगत या वास्तविक संख्याओं आदि पर सदिश रिक्त स्थान या मॉड्यूल (गणित) में सामान्यीकृत किया जाता है।[3]

चक्र का पता लगाना

निर्देशित और अप्रत्यक्ष ग्राफ़ में एक चक्र का अस्तित्व इस तथ्य पर निर्धारित किया जा सकता है कि क्या गहराई-प्रथम खोज (डीएफएस) को एक किनारा मिलता है जो वर्तमान शीर्ष के पूर्वज को इंगित करता है (इसमें गहराई-प्रथम खोज या गहराई-प्रथम खोज का आउटपुट सम्मिलित है).[4] इस प्रकार से सभी पिछले किनारे जिन पर डीएफएस छूट जाता है वे चक्रों का भाग होता हैं।[5] एक अप्रत्यक्ष ग्राफ़ में, किसी नोड के पैरेंट के किनारे को पिछले किनारे के रूप में नहीं गिना जाना चाहिए, किन्तु पहले से देखे गए किसी अन्य शीर्ष को खोजने से पिछले किनारे का संकेत देता है । अप्रत्यक्ष ग्राफ़ की स्तिथिया में, एन-वर्टेक्स ग्राफ़ में एक चक्र खोजने के लिए केवल O(n) समय की आवश्यकता होती है, क्योंकि अधिकतम n − 1 किनारे ट्री के किनारे हो सकते हैं।

अनेक टोपोलॉजिकल छँटाई एल्गोरिदम भी चक्रों का पता लगाएंगे, क्योंकि वे टोपोलॉजिकल ऑर्डर के अस्तित्व में बाधाएं हैं। इसके अतिरिक्त , यदि एक निर्देशित ग्राफ को दृढ़ता से जुड़े घटकों में विभाजित किया गया है, तो चक्र केवल घटकों के अन्दर उपस्तिथ होते हैं, उनके मध्य उपस्थित नहीं होते है , क्योंकि चक्र दृढ़ता से जुड़े होते हैं।[5]

इस प्रकार से निर्देशित ग्राफ़ के लिए, वितरित संदेश-आधारित एल्गोरिदम का उपयोग किया जा सकता है। ये एल्गोरिदम इस विचार पर विश्वाश करते हैं कि एक चक्र में एक शीर्ष द्वारा भेजा गया संदेश स्वयं वापस आ जाएगा।

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

चक्र पहचान के अनुप्रयोगों में समवर्ती प्रणालियों में गतिरोध का पता लगाने के लिए डेडलॉक का उपयोग सम्मिलित है।[6]

एल्गोरिथम

For every vertex v: visited(v) = false, finished(v) = false
For every vertex v:
  DFS(v)
DFS(v):
  if finished(v)
    return
  if visited(v)
    "Cycle found" and return
  visited(v) = true
  for every neighbour w
    DFS(w)
  finished(v) = true

नेबर का मतलब निर्देशित और अप्रत्यक्ष ग्राफ़ दोनों के लिए v से जुड़े सभी शीर्ष हैं, सिवाय उस शीर्ष को छोड़कर जिसे डीएफएस(वी) कहा जाता है। यह एल्गोरिथम को तुच्छ चक्रों को पकड़ने से भी बचाता है, जो कि लघु से लघु एक किनारे वाले प्रत्येक अप्रत्यक्ष ग्राफ़ में होता है।

प्रोग्रामिंग

प्रोग्रामिंग लैंग्वेज सी_शार्प_(प्रोग्रामिंग_लैंग्वेज ) सी# में निम्नलिखित उदाहरण एडजेंसी सूचियों का उपयोग करके एक अप्रत्यक्ष ग्राफ़ के एक कार्यान्वयन को दर्शाता है। अप्रत्यक्ष ग्राफ़ को क्लास_(कंप्यूटर_प्रोग्रामिंग) अनडायरेक्टेडग्राफ के रूप में घोषित किया गया है। प्रोग्राम को निष्पादित करने में मुख्य विधि_(कंप्यूटर_प्रोग्रामिंग) का उपयोग किया जाता है, जो - यदि कोई उपस्तिथ है - कंसोल पर सबसे छोटा, गैर-तुच्छ चक्र प्रिंट करता है।[7]

using System;                                                                                                                                                                                          
using System.Collections.Generic;                                                                                                                                                                                                                                         
                                                                                                                                                                                                                                                                                                                                      
// Declares the class for the vertices of the graph                                                                                                                                                      
class Node                                                                                                                                                                                                                                                                                                                                                                    
{                                                                                                                                                                                                                                                                                                                                        
	public int index;                                                                                                                                                          
	public string value;                                                                                                                                                                     
	public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Set of neighbour vertices                                                 
}                                                                                                                                                                                                                             
                                                                                                                                                                                   
// Declares the class for the undirected graph                                                         
class UndirectedGraph                                                                                                                                       
{                                                                                                                                                                                                                   
	public HashSet<Node> nodes = new HashSet<Node>();                                                                                                       
                                                                                                          	                                                                                                  
	// This method connects node1 and node2 with each other                                                                                        
	public void ConnectNodes(Node node1, Node node2)                                                                                                            
	{                                                                                                
		node1.adjacentNodes.Add(node2);                                                                                               
		node2.adjacentNodes.Add(node1);                                                                                                                            
	}                                                                                                                                                                                           
}                                                                                                                                                                                                                   
                                                                                                             
class Program                                                                                                                                                                    
{                                                                                                       
	// This method returns the cycle in the form A, B, C, ... as text.                                                                          
	public static string ToString(List<Node> cycle)                                                                                              
	{                                                                                                                                                                                            
		string text = "";                                                                       
		for (int i = 0; i < cycle.Count; i++) // for-loop, iterating the vertices                      
		{                                                                                        
			text += cycle[i].value + ", ";                                                                                                              
		}                                                                                          
		text = text.Substring(0, text.Length - 2);                                                                                                 
		return text;                                                                                                                                                           
	}                                                                                                                                              
	                                                 
	// Main method executing the program                                                                                                        
	public static void Main(string[] args)                                                                                                          
	{                                                                                                                                  
		Node node1 = new Node{index = 0, value = "A"};                                                                                       
		Node node2 = new Node{index = 1, value = "B"};                                                                                     
		Node node3 = new Node{index = 2, value = "C"};                                                                                         
		Node node4 = new Node{index = 3, value = "D"};                                                                                   
		// Declares and initialises an array holding the vertices                                     
		Node[] nodes = {node1, node2, node3, node4};                                              
		// Creates an undirected graph                                                                
		UndirectedGraph undirectedGraph = new UndirectedGraph();
		int numberOfNodes = nodes.Length;                                    
		for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices
		{                                                                                                                                                                                
			undirectedGraph.nodes.Add(nodes[i]); // Adds the vertices to the graph
		}                                                                                                                                                            
		// Connects the vertices of the graph with each other
		undirectedGraph.ConnectNodes(node1, node1);                                                                                             
		undirectedGraph.ConnectNodes(node1, node2);                                                  
		undirectedGraph.ConnectNodes(node2, node3);                                                   
		undirectedGraph.ConnectNodes(node3, node1);                                          
		undirectedGraph.ConnectNodes(node3, node4);                                                    
		undirectedGraph.ConnectNodes(node4, node1);                                                    
	                                                                                                	                                                                                        
		HashSet<Node> newNodes = new HashSet<Node>(nodes); // Set of new vertices to iterate
		HashSet<List<Node>> paths = new HashSet<List<Node>>(); // Set of current paths
		for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices of the graph
		{                                                                                                                                                                            
			Node node = nodes[i];
			newNodes.Add(node); // Add the vertex to the set of new vertices to iterate
			List<Node> path = new List<Node>();
			path.Add(node);                                                                    
			paths.Add(path); // Adds a path for each node as a starting vertex
		}                                                                                                                                                                                          
		HashSet<List<Node>> shortestCycles = new HashSet<List<Node>>(); // Set of shortest cycles
		int lengthOfCycles = 0; // Length of shortest cycles
		bool cyclesAreFound = false; // Whether or not cycles were found at all
		while (!cyclesAreFound && newNodes.Count > 0) // As long as we still had vertices to iterate                                                                                                       
		{                                                                                         
			newNodes.Clear(); // Empties the set of nodes to iterate
			HashSet<List<Node>> newPaths = new HashSet<List<Node>>(); // Set of newly found paths                                                  
			foreach (List<Node> path in paths) // foreach-loop, iterating all current paths
			{                                                            
				Node lastNode = path[path.Count - 1];
				newNodes.Add(lastNode); // Adds the final vertex of the path to the list of vertices to iterate                                                                                           
				foreach (Node nextNode in lastNode.adjacentNodes) // foreach-loop, iterating all neighbours of the previous node
				{
					if (path.Count >= 3 && path[0] == nextNode) // If a cycle with length greater or equal 3 was found
					{                                                       
						cyclesAreFound = true;
						shortestCycles.Add(path); // Adds the path to the set of cycles                                                                                                
						lengthOfCycles = path.Count;
					}                                                  
					if (!path.Contains(nextNode)) // If the path doesn't contain the neighbour                                                              
					{
						newNodes.Add(nextNode); // Adds the neighbour to the set of vertices to iterate                                                                                   
						// Creates a new path
						List<Node> newPath = new List<Node>();
						newPath.AddRange(path); // Adds the current path's vertex to the new path in the correct order                                                                     
						newPath.Add(nextNode); // Adds the neighbour to the new path                                                                 
						newPaths.Add(newPath); // Adds the path to the set of newly found paths                                                                   
					}                                   
				}                                                                             
			}                                                                                    
			paths = newPaths; // Updates the set of current paths
		}                                                               
		if (shortestCycles.Count > 0) // If cycles were found
		{                                                                                
			Console.WriteLine("The graph contains " + shortestCycles.Count + " cycles of length " + lengthOfCycles + "."); // Print to console
			foreach (List<Node> cycle in shortestCycles) // foreach-loop, iterating all found cycles                                                                   
			{                                                                   
				Console.WriteLine(ToString(cycle)); // Print to console
			}                                     
		}                                                                                         
		else                                                                                   
		{                                                                                           
			Console.WriteLine("The graph contains no cycles."); // Print to console
		}                                                                                              
		
		Console.ReadLine();                                                                          
	}                                                                                             
}

चक्र द्वारा ग्राफ़ को कवर करना

इस प्रकार से कोनिग्सबर्ग के सात पुलों पर अपने 1736 के पेपर में, जिसे व्यापक रूप से ग्राफ सिद्धांत का उत्पत्ति माना जाता है, लियोनहार्ड यूलर ने प्रमाणित किया कि, एक सीमित अप्रत्यक्ष ग्राफ के लिए एक बंद चाल होती है जो प्रत्येक किनारे पर पूर्ण रूप से जाती है (इसे बंद चिह्न बनाती है), यह आवश्यक और पर्याप्त है कि यह अलग-अलग शीर्षों को छोड़कर जुड़ा हो (अर्थात, सभी किनारे एक घटक में समाहित हों) और प्रत्येक शीर्ष पर सम डिग्री होती है । किन्तु निर्देशित ग्राफ़ में प्रत्येक किनारे पर पूर्ण रूप से जाने वाले बंद वॉक के अस्तित्व के लिए संबंधित लक्षण वर्णन यह है कि ग्राफ़ दृढ़ता से जुड़ा हुआ है और प्रत्येक शीर्ष पर आने वाले और बाहर जाने वाले किनारों की समान संख्या है। किसी भी स्थिति में, परिणामी बंद पथ को यूलेरियन पथ के रूप में जाना जाता है। यदि एक परिमित अप्रत्यक्ष ग्राफ के प्रत्येक शीर्ष पर सम डिग्री है, चाहे वह जुड़ा हुआ हो या नहीं, तो सरल चक्रों का एक समुच्च खोजना संभव है जो एक साथ प्रत्येक किनारे को पूर्ण रूप से एक बार कवर करते हैं: यह वेब्लेन का प्रमेय है।[8] जब एक कनेक्टेड ग्राफ यूलर के प्रमेय की नियम को पूर्ण नहीं करता है, तो मार्ग निरीक्षण समस्या को हल करके प्रत्येक किनारे को पूर्ण रूप से कवर करने वाली न्यूनतम लंबाई का एक बंद चलना बहुपद समय में पाया जा सकता है।

किन्तु एकल सरल चक्र खोजने की समस्या जो किनारों को कवर करने के अतिरिक्त प्रत्येक शीर्ष को पूर्ण रूप से कवर करती है, अधिक जटिल होते है। ऐसे चक्र को हैमिल्टनियन चक्र के रूप में जाना जाता है, और यह निर्धारित करना कि यह अस्तित्व में है या नहीं, एनपी-पूर्ण है।[9] ग्राफ़ के उन वर्गों के संबंध में अधिक शोध प्रकाशित किए गए हैं जिनमें हैमिल्टनियन चक्र सम्मिलित होने की प्रमाण दिया जा सकती है; इस प्रकार से उदाहरण ओरे का प्रमेय है कि एक हैमिल्टनियन चक्र सदैव एक ग्राफ़ में पाया जा सकता है जिसके लिए प्रत्येक गैर-आसन्न युग्म शीर्षों की डिग्री ग्राफ़ में कम से कम शीर्षों की कुल संख्या के समान होती है।[10]

अतः चक्र डबल कवर अनुमान बताता है कि, प्रत्येक ब्रिजलेस ग्राफ के लिए, सरल चक्रों का एक समूह उपस्तिथ होता है जो ग्राफ़ के प्रत्येक किनारे को ठीक दो बार कवर करता है। यह प्रमाणित करना कि यह सत्य है (या इसका प्रति उदाहरण खोजना ) जो की एक समस्या बनी हुई है।[11]

चक्र द्वारा परिभाषित ग्राफ वर्ग

ग्राफ़ के कई महत्वपूर्ण वर्गों को उनके चक्रों द्वारा परिभाषित या चित्रित किया जा सकता है। इसमे सम्मिलित है:

  • द्विदलीय ग्राफ, विषम चक्रों के बिना एक ग्राफ (विषम संख्या में शीर्षों वाला चक्र)
  • कैक्टस ग्राफ, एक ग्राफ़ जिसमें प्रत्येक गैर-तुच्छ द्विसंबद्ध घटक एक चक्र है ।
  • चक्र ग्राफ , एक ग्राफ़ जिसमें एक चक्र होता है।
  • कॉर्डल ग्राफ, एक ग्राफ जिसमें प्रत्येक प्रेरित चक्र एक त्रिकोण है।
  • निर्देशित चक्रीय ग्राफ, एक निर्देशित ग्राफ जिसमें कोई निर्देशित चक्र नहीं है।
  • रेखा पूर्ण ग्राफ, एक ऐसा ग्राफ जिसमें प्रत्येक विषम चक्र एक त्रिभुज होता है।

रेखा पूर्ण ग्राफ़, एक ऐसा ग्राफ जिसमें कोई प्रेरित चक्र या तीन से अधिक विषम लंबाई के उनके पूरक नहीं हैं।

  • छद्मवन, एक ग्राफ़ जिसमें प्रत्येक जुड़े घटक में अधिकतम एक चक्र होता है।
  • स्ट्रेगुलेटेड   ग्राफ, एक ग्राफ़ जिसमें प्रत्येक परिधीय चक्र एक त्रिकोण है।
  • जटिलता से जुड़ा ग्राफ, एक निर्देशित ग्राफ जिसमें हर किनारा एक चक्र का भाग है।
  • त्रिभुज-रहित ग्राफ़, तीन-शीर्ष चक्रों के बिना एक ग्राफ़ है।
  • सम-चक्र-फ्री ग्राफ, सम चक्रों के बिना एक ग्राफ है।
  • सम-छिद्र-फ्री ग्राफ़, 6 से उच्च या उसके समान लंबाई वाला सम-चक्र रहित ग्राफ़ है।

यह भी देखें

संदर्भ

  1. 1.0 1.1 1.2 1.3 Bender & Williamson 2010, p. 164.
  2. Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197–207, ISBN 9781584885054, archived from the original on 2023-02-04, retrieved 2016-09-27.
  3. Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28, archived from the original on 2023-02-04, retrieved 2016-09-27.
  4. Tucker, Alan (2006). "Chapter 2: Covering Circuits and Graph Colorings". एप्लाइड कॉम्बिनेटरिक्स (5th ed.). Hoboken: John Wiley & sons. p. 49. ISBN 978-0-471-73507-6.
  5. 5.0 5.1 Sedgewick, Robert (1983), "Graph algorithms", Algorithms, Addison–Wesley, ISBN 0-201-06672-6
  6. Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003). Operating System Concepts. John Wiley & Sons, INC. pp. 260. ISBN 0-471-25060-0.
  7. GeeksforGeeks: Shortest cycle in an undirected unweighted graph Archived 2022-01-11 at the Wayback Machine
  8. Veblen, Oswald (1912), "An Application of Modular Equations in Analysis Situs", Annals of Mathematics, Second Series, 14 (1): 86–94, doi:10.2307/1967604, JSTOR 1967604.
  9. Richard M. Karp (1972), "Reducibility Among Combinatorial Problems" (PDF), in R. E. Miller and J. W. Thatcher (ed.), Complexity of Computer Computations, New York: Plenum, pp. 85–103, archived (PDF) from the original on 2021-02-10, retrieved 2014-03-12.
  10. Ore, Ø. (1960), "Note on Hamilton circuits", American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928.
  11. Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, vol. 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1.