Circuit rank
ग्राफ सिद्धांत में, गणित की एक शाखा, सर्किट रैंक, साइक्लोमैटिक संख्या, चक्र रैंक, या एक अनिर्दिष्ट ग्राफ की शून्यता किनारों की न्यूनतम संख्या है जिसे ग्राफ से उसके सभी चक्रों को तोड़ने के लिए हटाया जाना चाहिए, जिससे यह एक पेड़ या जंगल बन जाता है। यह ग्राफ में स्वतंत्र चक्रों की संख्या (एक चक्र आधार का आकार) के बराबर है। निर्देशित ग्राफ के लिए संबंधित फीडबैक आर्क सेट समस्या के विपरीत, सर्किट रैंक की गणना आसानी से सूत्र का उपयोग करके की जाती है, जहां दिए गए ग्राफ में किनारों की संख्या है, शीर्षों की संख्या है, और जुड़े हुए घटकों की संख्या है। किनारों का एक न्यूनतम आकार का सेट बनाना भी संभव है जो सभी चक्रों को कुशलता से तोड़ता है, या तो एक लालची एल्गोरिदम का उपयोग करके या एक फैले हुए जंगल के पूरक के रूप में। परिपथ श्रेणी को बीजगणितीय ग्राफ सिद्धांत के संदर्भ में ग्राफ के चक्र स्थान के आयाम के रूप में, मैट्रायड सिद्धांत के संदर्भ में ग्राफिक मैट्रायड के कोरैंक के रूप में, और टोपोलॉजी के संदर्भ में ग्राफ से प्राप्त टोपोलॉजिकल स्थान की बेट्टी संख्याओं में से एक के रूप में समझाया जा सकता है। यह ग्राफ के कान के अपघटन में कानों की गिनती करता है, लगभग पेड़ों पर मानकीकृत जटिलता का आधार बनाता है, और कोड के एक टुकड़े की चक्रीय जटिलता की परिभाषा के हिस्से के रूप में सॉफ्टवेयर मेट्रिक्स में लागू किया गया है। साइक्लोमैटिक संख्या के नाम के तहत, अवधारणा को गुस्ताव किरचॉफ द्वारा पेश किया गया था। मैटरॉइड रैंक और न्यूनतम फीडबैक एज सेट का निर्माण एक ग्राफ की सर्किट रैंक को मैटरॉइड सिद्धांत का उपयोग करके मैटरॉइड के ग्राफिक मैटरॉइड के कोरैंक के रूप में वर्णित किया जा सकता है। मेट्रॉइड के लालची गुण का उपयोग करके, इसका मतलब है कि कोई भी ऐसे किनारों का एक न्यूनतम सेट पा सकता है जो एक लालची एल्गोरिथ्म का उपयोग करके सभी चक्रों को तोड़ता है जो प्रत्येक चरण में एक किनारे का चयन करता है जो शेष ग्राफ के कम से कम एक चक्र से संबंधित है। वैकल्पिक रूप से, किनारों का एक न्यूनतम समूह जो सभी चक्रों को तोड़ता है, एक फैले हुए जंगल का निर्माण करके और किनारों के पूरक समूह का चयन करके पाया जा सकता है जो फैले हुए जंगल से संबंधित नहीं हैं। स्वतंत्र चक्रों की संख्या बीजगणितीय ग्राफ सिद्धांत में, परिपथ श्रेणी भी चक्र स्थान का आयाम है। सहज रूप से, इसे इस अर्थ के रूप में समझाया जा सकता है कि परिपथ श्रेणी ग्राफ में स्वतंत्र चक्रों की संख्या को गिनती है, जहां चक्रों का एक संग्रह स्वतंत्र है यदि किसी एक चक्र को अन्य के कुछ उपसमुच्चय के सममित अंतर के रूप में बनाना संभव नहीं है। स्वतंत्र चक्रों की इस गिनती को टोपोलॉजी की एक शाखा, होमोलॉजी सिद्धांत का उपयोग करके भी समझाया जा सकता है। किसी भी ग्राफ को एक-आयामी सरल परिसर के उदाहरण के रूप में देखा जा सकता है, एक प्रकार का स्थलवैज्ञानिक स्थान जो एक रेखा खंड द्वारा प्रत्येक ग्राफ किनारे का प्रतिनिधित्व करके और इन रेखा खंडों को उनके अंतिम बिंदुओं पर एक साथ चिपकाकर बनाया जाता है। साइक्लोमैटिक संख्या इस परिसर के पहले (पूर्णांक) समरूपता समूह की श्रेणी है, इस टोपोलॉजिकल संबंध के कारण, एक ग्राफ की साइक्लोमैटिक संख्या को पहली बेट्टी संख्या भी कहा जाता है। अधिक आम तौर पर, किसी भी स्थलवैज्ञानिक स्थान की पहली बेट्टी संख्या, उसी तरह परिभाषित, अंतरिक्ष में स्वतंत्र चक्रों की संख्या को गिनती है। अनुप्रयोग मेशेडनेस गुणांक समतलीय ग्राफ के लिए परिपथ श्रेणी का एक प्रकार, जिसे एक ही शीर्ष समूह के साथ किसी भी समतलीय ग्राफ के अधिकतम संभव परिपथ श्रेणी से विभाजित करके सामान्यीकृत किया जाता है, को मेशेडनेस गुणांक कहा जाता है। किनारों और शीर्षों के साथ जुड़े समतलीय ग्राफ के लिए, जाली गुणांक की गणना सूत्र द्वारा की जा सकती है यहाँ, सूत्र का अंश दिए गए ग्राफ की परिपथ श्रेणी है, और भाजक एक-वर्टेक्स समतलीय ग्राफ की सबसे बड़ी संभव परिपथ श्रेणी है। मेशेडनेस गुणांक पेड़ों के लिए 0 और अधिकतम समतल ग्राफ के लिए 1 के बीच होता है। कान अपघटन परिपथ श्रेणी ग्राफ के कान अपघटन में कान की संख्या को नियंत्रित करती है, ग्राफ के किनारों का पथ और चक्रों में विभाजन जो कई ग्राफ एल्गोरिदम में उपयोगी है। विशेष रूप से, एक ग्राफ 2-वर्टेक्स से जुड़ा होता है यदि और केवल तभी जब इसमें खुले कान का अपघटन होता है। यह सबग्राफ का एक क्रम है, जहां पहला सबग्राफ एक सरल चक्र है, शेष सबग्राफ सभी सरल पथ हैं, प्रत्येक पथ पिछले सबग्राफ से संबंधित शीर्षों पर शुरू होता है और समाप्त होता है, और पथ का प्रत्येक आंतरिक शीर्ष उस पथ में पहली बार दिखाई देता है। सर्किट रैंक के साथ किसी भी बाइकनेक्टेड ग्राफ में, हर खुले कान के अपघटन में बिल्कुल कान होते हैं। साइक्लोमैटिक संख्या वाले ग्राफ को आर-अलमोस्ट-ट्री भी कहा जाता है, क्योंकि इसे पेड़ या जंगल बनाने के लिए ग्राफ से केवल आर किनारों को हटाने की आवश्यकता होती है। एक-निकटतम पेड़ एक निकट-पेड़ हैः एक जुड़ा हुआ निकट-पेड़ एक छद्म पेड़ है, एक चक्र जिसमें प्रत्येक शीर्ष पर जड़ें (संभवतः तुच्छ) पेड़ होती हैं। कई लेखकों ने आर-निकट-पेड़ों पर ग्राफ एल्गोरिदम की मानकीकृत जटिलता का अध्ययन किया है। निर्देशित ग्राफों के लिए सामान्यीकरण चक्र श्रेणी निर्देशित ग्राफों का एक अपरिवर्तनीय है जो ग्राफ में चक्रों के घोंसले के स्तर को मापता है। इसकी परिभाषा परिपथ श्रेणी की तुलना में अधिक जटिल है (दिशाहीन ग्राफ के लिए वृक्ष-गहराई की परिभाषा से निकटता से संबंधित) और इसकी गणना करना अधिक कठिन है। सर्किट रैंक से संबंधित निर्देशित ग्राफ के लिए एक और समस्या न्यूनतम प्रतिक्रिया चाप सेट है, किनारों का सबसे छोटा सेट जिसका निष्कासन सभी निर्देशित चक्रों को तोड़ देता है। साइकिल रैंक और न्यूनतम फीडबैक आर्क सेट दोनों की गणना करने के लिए एनपी-हार्ड हैं। किनारों की दिशाओं को नजरअंदाज करके और अंतर्निहित अनिर्दिष्ट ग्राफ की परिपथ श्रेणी की गणना करके निर्देशित ग्राफ के एक सरल अपरिवर्तनीय की गणना करना भी संभव है। यह सिद्धांत साइक्लोमैटिक जटिलता की परिभाषा का आधार बनाता है, जो यह अनुमान लगाने के लिए एक सॉफ्टवेयर मीट्रिक है कि कंप्यूटर कोड का एक टुकड़ा कितना जटिल है। कम्प्यूटेशनल रसायन विज्ञान रसायन विज्ञान और रसायन विज्ञान के क्षेत्रों में, एक आणविक ग्राफ की परिपथ श्रेणी (सबसे छोटे वलय के सबसे छोटे समूह में वलय की संख्या) को कभी-कभी फ्रेर्जैक संख्या के रूप में संदर्भित किया जाता है। मानकीकृत जटिलता ग्राफ पर कुछ कम्प्यूटेशनल समस्याएं सामान्य रूप से एन. पी.-कठोर होती हैं, लेकिन एक छोटे परिपथ श्रेणी वाले ग्राफ के लिए बहुपद समय में हल की जा सकती हैं। एक उदाहरण पथ पुनर्संयोजन समस्या है। संबंधित अवधारणाएँ ग्राफ से चीजों को हटाने के संदर्भ में परिभाषित अन्य संख्याएँ हैंः एज कनेक्टिविटी-ग्राफ को डिस्कनेक्ट करने के लिए हटाने के लिए किनारों की न्यूनतम संख्या; मिलान पूर्व-एक पूर्ण मिलान के अस्तित्व को रोकने के लिए हटाने के लिए किनारों की न्यूनतम संख्या; फीडबैक वर्टेक्स सेट संख्या-ग्राफ को एसाइक्लिक बनाने के लिए हटाने के लिए शीर्षों की न्यूनतम संख्या; फीडबैक आर्क सेट-एक निर्देशित ग्राफ से हटाने के लिए चापों की न्यूनतम संख्या, ताकि इसे एसाइक्लिक बनाया जा सके। संदर्भ ग्राफ अपरिवर्तनीय मैट्रायड सिद्धांत वृक्ष का फैलाव