परिधीय चक्र: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Graph cycle which does not separate remaining elements}} | {{short description|Graph cycle which does not separate remaining elements}} | ||
[[File:6n-graf-clique.svg|thumb|240px|इस ग्राफ़ में, 1, 2, और 5 शीर्षों द्वारा गठित लाल त्रिकोण परिधीय चक्र है: चार शेष किनारे सेतु बनाते हैं। चूँकि, पेंटागन 1-2-3-4-5 परिधीय नहीं है, क्योंकि दो शेष किनारे दो अलग-अलग सेतु बनाते हैं।]]ग्राफ़ सिद्धांत में, एक [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष ग्राफ़]] में परिधीय चक्र (या परिधीय | [[File:6n-graf-clique.svg|thumb|240px|इस ग्राफ़ में, 1, 2, और 5 शीर्षों द्वारा गठित लाल त्रिकोण परिधीय चक्र है: चार शेष किनारे सेतु बनाते हैं। चूँकि, पेंटागन 1-2-3-4-5 परिधीय नहीं है, क्योंकि दो शेष किनारे दो अलग-अलग सेतु बनाते हैं।]]ग्राफ़ सिद्धांत में, एक [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष ग्राफ़]] में परिधीय चक्र (या परिधीय परिपथ), सहज रूप से, चक्र (ग्राफ़ सिद्धांत) है जो ग्राफ़ के किसी भी भाग को किसी अन्य भाग से अलग नहीं करता है। परिधीय चक्र (या, जैसा कि उन्हें प्रारंभ में परिधीय बहुभुज कहा जाता था, क्योंकि टुट्टे ने चक्रों को "बहुभुज" कहा था) का अध्ययन सबसे पहले {{harvtxt|टुट्टे|1963}} द्वारा किया गया था और वे [[ प्लेनर ग्राफ |प्लेनर ग्राफ़]] के लक्षण वर्णन में और गैर-समतल ग्राफ़ के [[चक्र स्थान]] बनाने में महत्वपूर्ण भूमिका निभाते हैं।<ref>{{citation | ||
| last = Tutte | first = W. T. | author-link = W. T. Tutte | | last = Tutte | first = W. T. | author-link = W. T. Tutte | ||
| journal = Proceedings of the London Mathematical Society | | journal = Proceedings of the London Mathematical Society | ||
| Line 39: | Line 39: | ||
== गुण == | == गुण == | ||
परिधीय चक्र [[ बहुफलकीय ग्राफ | | परिधीय चक्र [[ बहुफलकीय ग्राफ |पॉलीहेड्रल ग्राफ़]] के सिद्धांत में दिखाई होते हैं, जो कि, [[के-वर्टेक्स-कनेक्टेड ग्राफ|3-शीर्ष-जुड़े समतल ग्राफ]] हैं। प्रत्येक समतल ग्राफ़ <math>G</math> के लिए, और <math>G</math> के प्रत्येक समतल एम्बेडिंग के लिए, प्रेरित चक्र वाले एम्बेडिंग के फलक परिधीय चक्र होने चाहिए। पॉलीहेड्रल ग्राफ में, सभी फलक परिधीय चक्र होते हैं, और प्रत्येक परिधीय चक्र एक फलक होता है।<ref>{{harvtxt|Tutte|1963}}, Theorems 2.7 and 2.8.</ref> यह इस तथ्य से अनुसरण करता है कि (संयोजी तुल्यता तक, बाहरी फलक की पसंद, और तल का अभिविन्यास) प्रत्येक पॉलीहेड्रल ग्राफ़ में अद्वितीय समतल एम्बेडिंग होता है।<ref>See the remarks following Theorem 2.8 in {{harvtxt|Tutte|1963}}. As Tutte observes, this was already known to {{citation | ||
| last = Whitney | first = Hassler | author-link = Hassler Whitney | | last = Whitney | first = Hassler | author-link = Hassler Whitney | ||
| doi = 10.2307/1989545 | | doi = 10.2307/1989545 | ||
| Line 50: | Line 50: | ||
| year = 1932 | jstor = 1989545 | doi-access = free | | year = 1932 | jstor = 1989545 | doi-access = free | ||
}}.</ref> | }}.</ref> | ||
समतल ग्राफ़ में, चक्र स्थान फलकों द्वारा उत्पन्न होता है, किन्तु गैर-समतल ग्राफ़ में परिधीय चक्र समान भूमिका निभाते हैं: प्रत्येक 3-शीर्ष-जुड़े परिमित ग्राफ़ के लिए, चक्र स्थान परिधीय चक्रों द्वारा उत्पन्न होता है।<ref>{{harvtxt|Tutte|1963}}, Theorem 2.5.</ref> परिणाम को स्थानीय रूप से परिमित किन्तु अनंत ग्राफ़ तक भी बढ़ाया जा सकता है।<ref>{{citation | |||
| last = Bruhn | first = Henning | | last = Bruhn | first = Henning | ||
| doi = 10.1016/j.jctb.2004.03.005 | | doi = 10.1016/j.jctb.2004.03.005 | ||
| Line 61: | Line 62: | ||
| volume = 92 | | volume = 92 | ||
| year = 2004| doi-access = free | | year = 2004| doi-access = free | ||
}}.</ref> विशेष रूप से, यह इस प्रकार है कि 3-जुड़े ग्राफ़ परिधीय चक्रों को | }}.</ref> विशेष रूप से, यह इस प्रकार है कि 3-जुड़े ग्राफ़ परिधीय चक्रों को सम्मिलित करने की गारंटी देते हैं। ऐसे 2-जुड़े ग्राफ़ उपस्थित हैं जिनमें परिधीय चक्र (उदाहरण [[पूर्ण द्विदलीय ग्राफ]] <math>K_{2,4}</math> हैं, जिसके लिए प्रत्येक चक्र में दो सेतु होते हैं) नहीं होते हैं किन्तु यदि 2-जुड़े ग्राफ़ में न्यूनतम डिग्री तीन है तो इसमें कम से कम परिधीय चक्र होता है।<ref>{{citation | ||
| last1 = Thomassen | first1 = Carsten | author1-link = Carsten Thomassen (mathematician) | | last1 = Thomassen | first1 = Carsten | author1-link = Carsten Thomassen (mathematician) | ||
| last2 = Toft | first2 = Bjarne | | last2 = Toft | first2 = Bjarne | ||
| Line 74: | Line 75: | ||
| year = 1981| doi-access = free | | year = 1981| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
3-जुड़े ग्राफों में परिधीय चक्रों की गणना रैखिक समय में की जा सकती है और इसका उपयोग ग्रहों के परीक्षणों को डिजाइन करने के लिए किया गया है।<ref>{{citation | 3-जुड़े ग्राफों में परिधीय चक्रों की गणना रैखिक समय में की जा सकती है और इसका उपयोग ग्रहों के परीक्षणों को डिजाइन करने के लिए किया गया है।<ref>{{citation | ||
| last1 = Schmidt | first1 = Jens M. | | last1 = Schmidt | first1 = Jens M. | ||
| Line 84: | Line 86: | ||
| isbn = 978-3-662-43947-0 | | isbn = 978-3-662-43947-0 | ||
}}.</ref> | }}.</ref> | ||
उन्हें गैर-पृथक कान अपघटन की अधिक सामान्य धारणा के लिए भी बढ़ाया गया था। ग्राफ़ की समतलता के परीक्षण के लिए कुछ एल्गोरिदम में, समस्या को छोटे उप-समस्याओं में विभाजित करने के लिए, ऐसे चक्र को खोजना उपयोगी होता है जो परिधीय नहीं है। तीन से कम [[सर्किट रैंक| | |||
उन्हें गैर-पृथक कान अपघटन की अधिक सामान्य धारणा के लिए भी बढ़ाया गया था। ग्राफ़ की समतलता के परीक्षण के लिए कुछ एल्गोरिदम में, समस्या को छोटे उप-समस्याओं में विभाजित करने के लिए, ऐसे चक्र को खोजना उपयोगी होता है जो परिधीय नहीं है। तीन से कम [[सर्किट रैंक|परिपथ रैंक]] के द्विसंबद्ध ग्राफ़ (जैसे [[चक्र ग्राफ|चक्र ग्राफ़]] या थीटा ग्राफ़) में प्रत्येक चक्र परिधीय होता है, किन्तु परिपथ रैंक तीन या अधिक के साथ प्रत्येक द्विसंबद्ध ग्राफ़ में गैर-परिधीय चक्र होता है, जो रैखिक समय में पाया जा सकता है।<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, Lemma 3.4, pp. 75–76.</ref> | |||
कोर्डल ग्राफ का सामान्यीकरण, {{harvtxt|सीमोर|वीवर|1984}} एक [[गला घोंटने वाला ग्राफ|स्ट्रैंगुलेटेड]] ग्राफ़ को एक ग्राफ के रूप में परिभाषित करता है जिसमें प्रत्येक परिधीय चक्र त्रिकोण है। वे इन ग्राफ़ों को कॉर्डल ग्राफ़ और अधिकतम प्लेनर ग्राफ़ के [[मैं एक गुट हूँ|क्लिक-सम]] के रूप में चिह्नित करते हैं।<ref>{{citation | |||
| last1 = Seymour | first1 = P. D. | author1-link = Paul Seymour (mathematician) | | last1 = Seymour | first1 = P. D. | author1-link = Paul Seymour (mathematician) | ||
| last2 = Weaver | first2 = R. W. | | last2 = Weaver | first2 = R. W. | ||
| Line 96: | Line 100: | ||
| volume = 8 | | volume = 8 | ||
| year = 1984}}.</ref> | | year = 1984}}.</ref> | ||
== संबंधित अवधारणाएं == | == संबंधित अवधारणाएं == | ||
परिधीय चक्रों को गैर-पृथक्करण चक्र भी कहा जाता है,<ref name="dett"/> | परिधीय चक्रों को गैर-पृथक्करण चक्र भी कहा जाता है,<ref name="dett"/>किन्तु यह शब्द अस्पष्ट है, क्योंकि इसका उपयोग दो संबंधित किन्तु अलग-अलग अवधारणाओं के लिए भी किया गया है: साधारण चक्र जिसे हटाने से शेष ग्राफ़ अलग हो जाएगा,<ref>E.g. see {{citation | ||
| last1 = Borse | first1 = Y. M. | | last1 = Borse | first1 = Y. M. | ||
| last2 = Waphare | first2 = B. N. | | last2 = Waphare | first2 = B. N. | ||
| Line 122: | Line 127: | ||
| year = 2007| doi-access = free | | year = 2007| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
मेट्रॉइड्स में, गैर-पृथक | मेट्रॉइड्स में, गैर-पृथक परिपथ [[ matroid |matroid]] का परिपथ है (जो कि, न्यूनतम निर्भर सेट है) जैसे कि [[माथेरॉइड माइनर]] परिपथ छोटे मैट्रोइड को छोड़ देता है जो जुड़ा हुआ है (अर्थात, जिसे मेट्रॉइड्स के प्रत्यक्ष योग के रूप में नहीं लिखा जा सकता है) ).<ref>{{citation | ||
| last1 = Maia | first1 = Bráulio, Junior | | last1 = Maia | first1 = Bráulio, Junior | ||
| last2 = Lemos | first2 = Manoel | | last2 = Lemos | first2 = Manoel | ||
| Line 135: | Line 140: | ||
| title = Combinatorics, complexity, and chance | | title = Combinatorics, complexity, and chance | ||
| volume = 34 | | volume = 34 | ||
| year = 2007}}.</ref> ये परिधीय चक्रों के अनुरूप हैं, | | year = 2007}}.</ref> ये परिधीय चक्रों के अनुरूप हैं, किन्तु [[ग्राफिक मैट्रोइड]]्स में भी समान नहीं हैं (मैट्रोड्स जिनके परिपथ ग्राफ़ के सरल चक्र हैं)। उदाहरण के लिए, पूर्ण द्विदलीय ग्राफ़ में <math>K_{2,3}</math>, प्रत्येक चक्र परिधीय है (इसमें केवल सेतु, दो-किनारे वाला मार्ग है) किन्तु इस सेतु द्वारा गठित ग्राफिक मैट्रॉइड जुड़ा नहीं है, इसलिए ग्राफिक मैट्रॉइड का कोई परिपथ नहीं है <math>K_{2,3}</math> अविभाज्य है। | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 07:12, 29 April 2023
ग्राफ़ सिद्धांत में, एक अप्रत्यक्ष ग्राफ़ में परिधीय चक्र (या परिधीय परिपथ), सहज रूप से, चक्र (ग्राफ़ सिद्धांत) है जो ग्राफ़ के किसी भी भाग को किसी अन्य भाग से अलग नहीं करता है। परिधीय चक्र (या, जैसा कि उन्हें प्रारंभ में परिधीय बहुभुज कहा जाता था, क्योंकि टुट्टे ने चक्रों को "बहुभुज" कहा था) का अध्ययन सबसे पहले टुट्टे (1963) द्वारा किया गया था और वे प्लेनर ग्राफ़ के लक्षण वर्णन में और गैर-समतल ग्राफ़ के चक्र स्थान बनाने में महत्वपूर्ण भूमिका निभाते हैं।[1]
परिभाषाएँ
परिधीय चक्र ग्राफ़ में औपचारिक रूप से कई समकक्ष विधियों में से में परिभाषित किया जा सकता है:
- परिधीय है यदि यह गुण के साथ जुड़े ग्राफ़ में साधारण चक्र है, जो कि में प्रत्येक दो किनारों और के लिए में एक पथ उपस्थित है, और इसी के साथ समाप्त होता है, और से संबंधित कोई आंतरिक शीर्ष नहीं है।[2]
- परिधीय है यदि यह संपत्ति के साथ एक प्रेरित चक्र है जो कि के किनारों और कोने को हटाकर गठित उपग्राफ जुड़ा हुआ है।[3]
- यदि , का कोई सबग्राफ है, तो का एक सेतु[4] का एक न्यूनतम सबग्राफ है जो कि से एज-डिसजॉइंट है और उसके पास वह गुण है जो उसके संलग्नक के सभी बिंदु ( और दोनों में किनारों से सटे शीर्ष) C से संबंधित हैं।[5] एक साधारण चक्र परिधीय है यदि इसमें ठीक सेतु है।[6]
इन परिभाषाओं की समानता को देखना कठिन नहीं है: का जुड़ा हुआ सबग्राफ (साथ में इसे से जोड़ने वाले किनारों के साथ), या चक्र का तार जो इसे प्रेरित करने में असफल होने का कारण बनता है, दोनों स्थितियों में एक सेतु होना चाहिए, और किनारों पर द्विआधारी संबंध का समकक्ष वर्ग भी होना चाहिए जिसमें दो किनारे आपस में जुड़े हुए हैं यदि वे में बिना किसी आंतरिक शीर्ष वाले पथ के छोर हैं।[7]
गुण
परिधीय चक्र पॉलीहेड्रल ग्राफ़ के सिद्धांत में दिखाई होते हैं, जो कि, 3-शीर्ष-जुड़े समतल ग्राफ हैं। प्रत्येक समतल ग्राफ़ के लिए, और के प्रत्येक समतल एम्बेडिंग के लिए, प्रेरित चक्र वाले एम्बेडिंग के फलक परिधीय चक्र होने चाहिए। पॉलीहेड्रल ग्राफ में, सभी फलक परिधीय चक्र होते हैं, और प्रत्येक परिधीय चक्र एक फलक होता है।[8] यह इस तथ्य से अनुसरण करता है कि (संयोजी तुल्यता तक, बाहरी फलक की पसंद, और तल का अभिविन्यास) प्रत्येक पॉलीहेड्रल ग्राफ़ में अद्वितीय समतल एम्बेडिंग होता है।[9]
समतल ग्राफ़ में, चक्र स्थान फलकों द्वारा उत्पन्न होता है, किन्तु गैर-समतल ग्राफ़ में परिधीय चक्र समान भूमिका निभाते हैं: प्रत्येक 3-शीर्ष-जुड़े परिमित ग्राफ़ के लिए, चक्र स्थान परिधीय चक्रों द्वारा उत्पन्न होता है।[10] परिणाम को स्थानीय रूप से परिमित किन्तु अनंत ग्राफ़ तक भी बढ़ाया जा सकता है।[11] विशेष रूप से, यह इस प्रकार है कि 3-जुड़े ग्राफ़ परिधीय चक्रों को सम्मिलित करने की गारंटी देते हैं। ऐसे 2-जुड़े ग्राफ़ उपस्थित हैं जिनमें परिधीय चक्र (उदाहरण पूर्ण द्विदलीय ग्राफ हैं, जिसके लिए प्रत्येक चक्र में दो सेतु होते हैं) नहीं होते हैं किन्तु यदि 2-जुड़े ग्राफ़ में न्यूनतम डिग्री तीन है तो इसमें कम से कम परिधीय चक्र होता है।[12]
3-जुड़े ग्राफों में परिधीय चक्रों की गणना रैखिक समय में की जा सकती है और इसका उपयोग ग्रहों के परीक्षणों को डिजाइन करने के लिए किया गया है।[13]
उन्हें गैर-पृथक कान अपघटन की अधिक सामान्य धारणा के लिए भी बढ़ाया गया था। ग्राफ़ की समतलता के परीक्षण के लिए कुछ एल्गोरिदम में, समस्या को छोटे उप-समस्याओं में विभाजित करने के लिए, ऐसे चक्र को खोजना उपयोगी होता है जो परिधीय नहीं है। तीन से कम परिपथ रैंक के द्विसंबद्ध ग्राफ़ (जैसे चक्र ग्राफ़ या थीटा ग्राफ़) में प्रत्येक चक्र परिधीय होता है, किन्तु परिपथ रैंक तीन या अधिक के साथ प्रत्येक द्विसंबद्ध ग्राफ़ में गैर-परिधीय चक्र होता है, जो रैखिक समय में पाया जा सकता है।[14]
कोर्डल ग्राफ का सामान्यीकरण, सीमोर & वीवर (1984) एक स्ट्रैंगुलेटेड ग्राफ़ को एक ग्राफ के रूप में परिभाषित करता है जिसमें प्रत्येक परिधीय चक्र त्रिकोण है। वे इन ग्राफ़ों को कॉर्डल ग्राफ़ और अधिकतम प्लेनर ग्राफ़ के क्लिक-सम के रूप में चिह्नित करते हैं।[15]
संबंधित अवधारणाएं
परिधीय चक्रों को गैर-पृथक्करण चक्र भी कहा जाता है,[2]किन्तु यह शब्द अस्पष्ट है, क्योंकि इसका उपयोग दो संबंधित किन्तु अलग-अलग अवधारणाओं के लिए भी किया गया है: साधारण चक्र जिसे हटाने से शेष ग्राफ़ अलग हो जाएगा,[16] और ग्राफ़ एम्बेडिंग के चक्र जैसे कि चक्र के साथ काटने से उस सतह को डिस्कनेक्ट नहीं किया जाएगा जिस पर ग्राफ़ एम्बेड किया गया है।[17] मेट्रॉइड्स में, गैर-पृथक परिपथ matroid का परिपथ है (जो कि, न्यूनतम निर्भर सेट है) जैसे कि माथेरॉइड माइनर परिपथ छोटे मैट्रोइड को छोड़ देता है जो जुड़ा हुआ है (अर्थात, जिसे मेट्रॉइड्स के प्रत्यक्ष योग के रूप में नहीं लिखा जा सकता है) ).[18] ये परिधीय चक्रों के अनुरूप हैं, किन्तु ग्राफिक मैट्रोइड्स में भी समान नहीं हैं (मैट्रोड्स जिनके परिपथ ग्राफ़ के सरल चक्र हैं)। उदाहरण के लिए, पूर्ण द्विदलीय ग्राफ़ में , प्रत्येक चक्र परिधीय है (इसमें केवल सेतु, दो-किनारे वाला मार्ग है) किन्तु इस सेतु द्वारा गठित ग्राफिक मैट्रॉइड जुड़ा नहीं है, इसलिए ग्राफिक मैट्रॉइड का कोई परिपथ नहीं है अविभाज्य है।
संदर्भ
- ↑ Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, Third Series, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387.
- ↑ 2.0 2.1 Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 74–75, ISBN 978-0-13-301615-4.
- ↑ This is, essentially, the definition used by Bruhn (2004). However, Bruhn distinguishes the case that