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