परिधीय चक्र: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|Graph cycle which does not separate remaining elements}} File:6n-graf-clique.svg|thumb|240px|इस ग्राफ में, 1, 2, और 5 शीर...")
 
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 परिधीय नहीं है, क्योंकि दो शेष किनारे दो अलग-अलग पुल बनाते हैं।]]ग्राफ़ सिद्धांत में, एक [[अप्रत्यक्ष ग्राफ]]़ में एक परिधीय चक्र (या परिधीय सर्किट), सहज रूप से, एक चक्र (ग्राफ़ सिद्धांत) है जो ग्राफ़ के किसी भी भाग को किसी अन्य भाग से अलग नहीं करता है। परिधीय चक्र (या, जैसा कि उन्हें शुरू में कहा जाता था, परिधीय बहुभुज, क्योंकि [[ सभी ]] चक्र बहुभुज कहलाते हैं) का अध्ययन सबसे पहले किसके द्वारा किया गया था {{harvtxt|Tutte|1963}}, और [[ प्लेनर ग्राफ ]]़ के लक्षण वर्णन में और नॉनप्लानर ग्राफ़ के [[चक्र स्थान]] बनाने में महत्वपूर्ण भूमिका निभाते हैं।<ref>{{citation
[[File:6n-graf-clique.svg|thumb|240px|इस ग्राफ में, 1, 2, और 5 शीर्षों द्वारा गठित लाल त्रिकोण परिधीय चक्र है: चार शेष किनारे पुल बनाते हैं। हालाँकि, पेंटागन 1-2-3-4-5 परिधीय नहीं है, क्योंकि दो शेष किनारे दो अलग-अलग पुल बनाते हैं।]]ग्राफ़ सिद्धांत में, [[अप्रत्यक्ष ग्राफ]]़ में परिधीय चक्र (या परिधीय सर्किट), सहज रूप से, चक्र (ग्राफ़ सिद्धांत) है जो ग्राफ़ के किसी भी भाग को किसी अन्य भाग से अलग नहीं करता है। परिधीय चक्र (या, जैसा कि उन्हें शुरू में कहा जाता था, परिधीय बहुभुज, क्योंकि [[ सभी ]] चक्र बहुभुज कहलाते हैं) का अध्ययन सबसे पहले किसके द्वारा किया गया था {{harvtxt|Tutte|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 13: Line 13:


== परिभाषाएँ ==
== परिभाषाएँ ==
एक परिधीय चक्र <math>C</math> एक ग्राफ में <math>G</math> औपचारिक रूप से कई समकक्ष तरीकों में से एक में परिभाषित किया जा सकता है:
परिधीय चक्र <math>C</math> ग्राफ में <math>G</math> औपचारिक रूप से कई समकक्ष तरीकों में से में परिभाषित किया जा सकता है:
*<math>C</math> परिधीय है यदि यह संपत्ति के साथ जुड़े ग्राफ में एक साधारण चक्र है, जो हर दो किनारों के लिए है <math>e_1</math> और <math>e_2</math> में <math>G\setminus C</math>, में एक पथ मौजूद है <math>G</math> से शुरू होता है <math>e_1</math>, इसी के साथ समाप्त होता है <math>e_2</math>, और इससे संबंधित कोई आंतरिक शीर्ष नहीं है <math>C</math>.<ref name="dett">{{citation
*<math>C</math> परिधीय है यदि यह संपत्ति के साथ जुड़े ग्राफ में साधारण चक्र है, जो हर दो किनारों के लिए है <math>e_1</math> और <math>e_2</math> में <math>G\setminus C</math>, में पथ मौजूद है <math>G</math> से शुरू होता है <math>e_1</math>, इसी के साथ समाप्त होता है <math>e_2</math>, और इससे संबंधित कोई आंतरिक शीर्ष नहीं है <math>C</math>.<ref name="dett">{{citation
  | last1 = Di Battista | first1 = Giuseppe
  | last1 = Di Battista | first1 = Giuseppe
  | last2 = Eades | first2 = Peter | author2-link = Peter Eades
  | last2 = Eades | first2 = Peter | author2-link = Peter Eades
Line 24: Line 24:
  | title = Graph Drawing: Algorithms for the Visualization of Graphs
  | title = Graph Drawing: Algorithms for the Visualization of Graphs
  | year = 1998}}.</ref>
  | year = 1998}}.</ref>
*<math>C</math> परिधीय है अगर यह सबग्राफ की संपत्ति के साथ एक [[प्रेरित चक्र]] है <math>G\setminus C</math> के किनारों और शीर्षों को हटाकर बनाया गया है <math>C</math> जुड़ा है।<ref>This is, essentially, the definition used by {{harvtxt|Bruhn|2004}}. However, Bruhn distinguishes the case that <math>G</math> has isolated vertices from disconnections caused by the removal of <math>C</math>.</ref>
*<math>C</math> परिधीय है अगर यह सबग्राफ की संपत्ति के साथ [[प्रेरित चक्र]] है <math>G\setminus C</math> के किनारों और शीर्षों को हटाकर बनाया गया है <math>C</math> जुड़ा है।<ref>This is, essentially, the definition used by {{harvtxt|Bruhn|2004}}. However, Bruhn distinguishes the case that <math>G</math> has isolated vertices from disconnections caused by the removal of <math>C</math>.</ref>
*अगर <math>C</math> का कोई सबग्राफ है <math>G</math>, एक पुल<ref>Not to be confused with [[bridge (graph theory)]], a different concept.</ref> का <math>C</math> एक न्यूनतम सबग्राफ है <math>B</math> का <math>G</math> वह किनारे से अलग है <math>C</math> और उसके पास वह संपत्ति है जो उसके संलग्नक के सभी बिंदु (दोनों में किनारों से सटे हुए कोने <math>B</math> और <math>G\setminus B</math>) के संबंधित <math>C</math>.<ref>{{citation
*अगर <math>C</math> का कोई सबग्राफ है <math>G</math>, पुल<ref>Not to be confused with [[bridge (graph theory)]], a different concept.</ref> का <math>C</math> न्यूनतम सबग्राफ है <math>B</math> का <math>G</math> वह किनारे से अलग है <math>C</math> और उसके पास वह संपत्ति है जो उसके संलग्नक के सभी बिंदु (दोनों में किनारों से सटे हुए कोने <math>B</math> और <math>G\setminus B</math>) के संबंधित <math>C</math>.<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 34: Line 34:
  | volume = 10
  | volume = 10
  | year = 1960
  | year = 1960
  | doi = 10.1112/plms/s3-10.1.304}}.</ref> एक साधारण चक्र <math>C</math> परिधीय है यदि इसमें ठीक एक सेतु है।<ref>This is the definition of peripheral cycles originally used by {{harvtxt|Tutte|1963}}. {{harvtxt|Seymour|Weaver|1984}} use the same definition of a peripheral cycle, but with a different definition of a bridge that more closely resembles the induced-cycle definition for peripheral cycles.</ref>
  | doi = 10.1112/plms/s3-10.1.304}}.</ref> साधारण चक्र <math>C</math> परिधीय है यदि इसमें ठीक सेतु है।<ref>This is the definition of peripheral cycles originally used by {{harvtxt|Tutte|1963}}. {{harvtxt|Seymour|Weaver|1984}} use the same definition of a peripheral cycle, but with a different definition of a bridge that more closely resembles the induced-cycle definition for peripheral cycles.</ref>
इन परिभाषाओं की समानता को देखना कठिन नहीं है: का एक जुड़ा हुआ सबग्राफ <math>G\setminus C</math> (साथ में इसे जोड़ने वाले किनारों के साथ <math>C</math>), या एक चक्र का तार जो इसे प्रेरित करने में असफल होने का कारण बनता है, दोनों मामलों में एक पुल होना चाहिए, और किनारों पर [[द्विआधारी संबंध]] का समकक्ष वर्ग भी होना चाहिए जिसमें दो किनारे संबंधित हैं यदि वे अंत हैं एक पथ जिसमें कोई आंतरिक शीर्ष नहीं है <math>C</math>.<ref>See e.g. Theorem 2.4 of {{harvtxt|Tutte|1960}}, showing that the vertex sets of bridges are path-connected, see {{harvtxt|Seymour|Weaver|1984}} for a definition of bridges using chords and connected components, and also see {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}} for a definition of bridges using equivalence classes of the binary relation on edges.</ref>
इन परिभाषाओं की समानता को देखना कठिन नहीं है: का जुड़ा हुआ सबग्राफ <math>G\setminus C</math> (साथ में इसे जोड़ने वाले किनारों के साथ <math>C</math>), या चक्र का तार जो इसे प्रेरित करने में असफल होने का कारण बनता है, दोनों मामलों में पुल होना चाहिए, और किनारों पर [[द्विआधारी संबंध]] का समकक्ष वर्ग भी होना चाहिए जिसमें दो किनारे संबंधित हैं यदि वे अंत हैं पथ जिसमें कोई आंतरिक शीर्ष नहीं है <math>C</math>.<ref>See e.g. Theorem 2.4 of {{harvtxt|Tutte|1960}}, showing that the vertex sets of bridges are path-connected, see {{harvtxt|Seymour|Weaver|1984}} for a definition of bridges using chords and connected components, and also see {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}} for a definition of bridges using equivalence classes of the binary relation on edges.</ref>




== गुण ==
== गुण ==
परिधीय चक्र [[ बहुफलकीय ग्राफ ]]़ के सिद्धांत में प्रकट होते हैं, जो कि, [[के-वर्टेक्स-कनेक्टेड ग्राफ]]़ | 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
परिधीय चक्र [[ बहुफलकीय ग्राफ ]]़ के सिद्धांत में प्रकट होते हैं, जो कि, [[के-वर्टेक्स-कनेक्टेड ग्राफ]]़ | 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 61: Line 61:
  | volume = 92
  | volume = 92
  | year = 2004| doi-access = free
  | year = 2004| doi-access = free
  }}.</ref> विशेष रूप से, यह इस प्रकार है कि 3-जुड़े ग्राफ़ परिधीय चक्रों को शामिल करने की गारंटी देते हैं। 2-कनेक्टेड ग्राफ़ मौजूद हैं जिनमें परिधीय चक्र नहीं होते हैं (एक उदाहरण [[पूर्ण द्विदलीय ग्राफ]]़ है <math>K_{2,4}</math>, जिसके लिए प्रत्येक चक्र में दो पुल होते हैं) लेकिन यदि 2-कनेक्टेड ग्राफ़ में न्यूनतम डिग्री तीन है तो इसमें कम से कम एक परिधीय चक्र होता है।<ref>{{citation
  }}.</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 84: Line 84:
  | 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>
उन्हें गैर-पृथक कान अपघटन की अधिक सामान्य धारणा के लिए भी बढ़ाया गया था। ग्राफ़ की समतलता के परीक्षण के लिए कुछ एल्गोरिदम में, समस्या को छोटे उप-समस्याओं में विभाजित करने के लिए, ऐसे चक्र को खोजना उपयोगी होता है जो परिधीय नहीं है। तीन से कम [[सर्किट रैंक]] के द्विसंबद्ध ग्राफ में (जैसे [[चक्र ग्राफ]] या ग्राफ सिद्धांत की शब्दावली#चलता है) प्रत्येक चक्र परिधीय होता है, लेकिन सर्किट रैंक तीन या अधिक के साथ प्रत्येक द्विसंबद्ध ग्राफ में गैर-परिधीय चक्र होता है, जो पाया जा सकता है रैखिक समय में।<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, Lemma 3.4, pp. 75–76.</ref>
तारकीय रेखांकन का सामान्यीकरण, {{harvtxt|Seymour|Weaver|1984}} एक [[गला घोंटने वाला ग्राफ]] को एक ग्राफ़ के रूप में परिभाषित करें जिसमें प्रत्येक परिधीय चक्र एक त्रिकोण है। वे इन ग्राफ़ों को कॉर्डल ग्राफ़ और अधिकतम प्लेनर ग्राफ़ के [[मैं एक गुट हूँ]] के रूप में चिह्नित करते हैं।<ref>{{citation
तारकीय रेखांकन का सामान्यीकरण, {{harvtxt|Seymour|Weaver|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 110: Line 110:
  | title = Vertex disjoint non-separating cycles in graphs
  | title = Vertex disjoint non-separating cycles in graphs
  | volume = 75
  | volume = 75
  | year = 2008}}.</ref> और एक [[ग्राफ एम्बेडिंग]] के चक्र जैसे कि चक्र के साथ काटने से उस सतह को डिस्कनेक्ट नहीं किया जाएगा जिस पर ग्राफ़ एम्बेड किया गया है।<ref>E.g. see {{citation
  | year = 2008}}.</ref> और [[ग्राफ एम्बेडिंग]] के चक्र जैसे कि चक्र के साथ काटने से उस सतह को डिस्कनेक्ट नहीं किया जाएगा जिस पर ग्राफ़ एम्बेड किया गया है।<ref>E.g. see {{citation
  | last1 = Cabello | first1 = Sergio
  | last1 = Cabello | first1 = Sergio
  | last2 = Mohar | first2 = Bojan
  | last2 = Mohar | first2 = Bojan
Line 122: Line 122:
  | year = 2007| doi-access = free
  | year = 2007| doi-access = free
  }}.</ref>
  }}.</ref>
मेट्रॉइड्स में, एक गैर-पृथक सर्किट [[ matroid ]] का एक सर्किट है (जो कि, एक न्यूनतम निर्भर सेट है) जैसे कि [[माथेरॉइड माइनर]] सर्किट एक छोटे मैट्रोइड को छोड़ देता है जो जुड़ा हुआ है (अर्थात, जिसे मेट्रॉइड्स के प्रत्यक्ष योग के रूप में नहीं लिखा जा सकता है) ).<ref>{{citation
मेट्रॉइड्स में, गैर-पृथक सर्किट [[ 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 135:
  | title = Combinatorics, complexity, and chance
  | title = Combinatorics, complexity, and chance
  | volume = 34
  | volume = 34
  | year = 2007}}.</ref> ये परिधीय चक्रों के अनुरूप हैं, लेकिन [[ग्राफिक मैट्रोइड]]्स में भी समान नहीं हैं (मैट्रोड्स जिनके सर्किट ग्राफ के सरल चक्र हैं)। उदाहरण के लिए, पूर्ण द्विदलीय ग्राफ में <math>K_{2,3}</math>, प्रत्येक चक्र परिधीय है (इसमें केवल एक पुल, एक दो-किनारे वाला मार्ग है) लेकिन इस पुल द्वारा गठित ग्राफिक मैट्रॉइड जुड़ा नहीं है, इसलिए ग्राफिक मैट्रॉइड का कोई सर्किट नहीं है <math>K_{2,3}</math> अविभाज्य है।
  | year = 2007}}.</ref> ये परिधीय चक्रों के अनुरूप हैं, लेकिन [[ग्राफिक मैट्रोइड]]्स में भी समान नहीं हैं (मैट्रोड्स जिनके सर्किट ग्राफ के सरल चक्र हैं)। उदाहरण के लिए, पूर्ण द्विदलीय ग्राफ में <math>K_{2,3}</math>, प्रत्येक चक्र परिधीय है (इसमें केवल पुल, दो-किनारे वाला मार्ग है) लेकिन इस पुल द्वारा गठित ग्राफिक मैट्रॉइड जुड़ा नहीं है, इसलिए ग्राफिक मैट्रॉइड का कोई सर्किट नहीं है <math>K_{2,3}</math> अविभाज्य है।


==संदर्भ==
==संदर्भ==

Revision as of 18:55, 28 April 2023

इस ग्राफ में, 1, 2, और 5 शीर्षों द्वारा गठित लाल त्रिकोण परिधीय चक्र है: चार शेष किनारे पुल बनाते हैं। हालाँकि, पेंटागन 1-2-3-4-5 परिधीय नहीं है, क्योंकि दो शेष किनारे दो अलग-अलग पुल बनाते हैं।

ग्राफ़ सिद्धांत में, अप्रत्यक्ष ग्राफ़ में परिधीय चक्र (या परिधीय सर्किट), सहज रूप से, चक्र (ग्राफ़ सिद्धांत) है जो ग्राफ़ के किसी भी भाग को किसी अन्य भाग से अलग नहीं करता है। परिधीय चक्र (या, जैसा कि उन्हें शुरू में कहा जाता था, परिधीय बहुभुज, क्योंकि सभी चक्र बहुभुज कहलाते हैं) का अध्ययन सबसे पहले किसके द्वारा किया गया था Tutte (1963), और प्लेनर ग्राफ ़ के लक्षण वर्णन में और नॉनप्लानर ग्राफ़ के चक्र स्थान बनाने में महत्वपूर्ण भूमिका निभाते हैं।[1]


परिभाषाएँ

परिधीय चक्र ग्राफ में औपचारिक रूप से कई समकक्ष तरीकों में से में परिभाषित किया जा सकता है:

  • परिधीय है यदि यह संपत्ति के साथ जुड़े ग्राफ में साधारण चक्र है, जो हर दो किनारों के लिए है और में , में पथ मौजूद है से शुरू होता है , इसी के साथ समाप्त होता है , और इससे संबंधित कोई आंतरिक शीर्ष नहीं है .[2]
  • परिधीय है अगर यह सबग्राफ की संपत्ति के साथ प्रेरित चक्र है के किनारों और शीर्षों को हटाकर बनाया गया है जुड़ा है।[3]
  • अगर का कोई सबग्राफ है , पुल[4] का न्यूनतम सबग्राफ है का वह किनारे से अलग है और उसके पास वह संपत्ति है जो उसके संलग्नक के सभी बिंदु (दोनों में किनारों से सटे हुए कोने और ) के संबंधित .[5] साधारण चक्र परिधीय है यदि इसमें ठीक सेतु है।[6]

इन परिभाषाओं की समानता को देखना कठिन नहीं है: का जुड़ा हुआ सबग्राफ (साथ में इसे जोड़ने वाले किनारों के साथ ), या चक्र का तार जो इसे प्रेरित करने में असफल होने का कारण बनता है, दोनों मामलों में पुल होना चाहिए, और किनारों पर द्विआधारी संबंध का समकक्ष वर्ग भी होना चाहिए जिसमें दो किनारे संबंधित हैं यदि वे अंत हैं पथ जिसमें कोई आंतरिक शीर्ष नहीं है .[7]


गुण

परिधीय चक्र बहुफलकीय ग्राफ ़ के सिद्धांत में प्रकट होते हैं, जो कि, के-वर्टेक्स-कनेक्टेड ग्राफ़ | 3-वर्टेक्स-कनेक्टेड प्लानर ग्राफ़ हैं। हर प्लानर ग्राफ के लिए , और हर प्लानर एम्बेडिंग , एम्बेडिंग के चेहरे जो प्रेरित चक्र हैं, परिधीय चक्र होने चाहिए। बहुफलकीय ग्राफ में, सभी फलक परिधीय चक्र होते हैं, और प्रत्येक परिधीय चक्र फलक होता है।[8] यह इस तथ्य से अनुसरण करता है कि (कॉम्बिनेटरियल तुल्यता तक, बाहरी चेहरे की पसंद, और विमान का अभिविन्यास) प्रत्येक पॉलीहेड्रल ग्राफ में अद्वितीय प्लानर एम्बेडिंग होता है।[9] प्लानर ग्राफ़ में, चक्र स्थान चेहरों द्वारा उत्पन्न होता है, लेकिन गैर-प्लानर ग्राफ़ में परिधीय चक्र समान भूमिका निभाते हैं: प्रत्येक 3-वर्टेक्स-कनेक्टेड परिमित ग्राफ़ के लिए, चक्र स्थान परिधीय चक्रों द्वारा उत्पन्न होता है।[10] परिणाम को स्थानीय रूप से परिमित लेकिन अनंत ग्राफ़ तक भी बढ़ाया जा सकता है।[11] विशेष रूप से, यह इस प्रकार है कि 3-जुड़े ग्राफ़ परिधीय चक्रों को शामिल करने की गारंटी देते हैं। 2-कनेक्टेड ग्राफ़ मौजूद हैं जिनमें परिधीय चक्र नहीं होते हैं (उदाहरण पूर्ण द्विदलीय ग्राफ़ है , जिसके लिए प्रत्येक चक्र में दो पुल होते हैं) लेकिन यदि 2-कनेक्टेड ग्राफ़ में न्यूनतम डिग्री तीन है तो इसमें कम से कम परिधीय चक्र होता है।[12] 3-जुड़े ग्राफों में परिधीय चक्रों की गणना रैखिक समय में की जा सकती है और इसका उपयोग ग्रहों के परीक्षणों को डिजाइन करने के लिए किया गया है।[13] उन्हें गैर-पृथक कान अपघटन की अधिक सामान्य धारणा के लिए भी बढ़ाया गया था। ग्राफ़ की समतलता के परीक्षण के लिए कुछ एल्गोरिदम में, समस्या को छोटे उप-समस्याओं में विभाजित करने के लिए, ऐसे चक्र को खोजना उपयोगी होता है जो परिधीय नहीं है। तीन से कम सर्किट रैंक के द्विसंबद्ध ग्राफ में (जैसे चक्र ग्राफ या ग्राफ सिद्धांत की शब्दावली#चलता है) प्रत्येक चक्र परिधीय होता है, लेकिन सर्किट रैंक तीन या अधिक के साथ प्रत्येक द्विसंबद्ध ग्राफ में गैर-परिधीय चक्र होता है, जो पाया जा सकता है रैखिक समय में।[14] तारकीय रेखांकन का सामान्यीकरण, Seymour & Weaver (1984) गला घोंटने वाला ग्राफ को ग्राफ़ के रूप में परिभाषित करें जिसमें प्रत्येक परिधीय चक्र त्रिकोण है। वे इन ग्राफ़ों को कॉर्डल ग्राफ़ और अधिकतम प्लेनर ग्राफ़ के मैं गुट हूँ के रूप में चिह्नित करते हैं।[15]


संबंधित अवधारणाएं

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

संदर्भ

  1. ↑ 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. ↑ 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.
  3. ↑ This is, essentially, the definition used by Bruhn (2004). However, Bruhn distinguishes the case that has isolated vertices from disconnections caused by the removal of .
  4. ↑ Not to be confused with bridge (graph theory), a different concept.
  5. ↑ Tutte, W. T. (1960), "Convex representations of graphs", Proceedings of the London Mathematical Society, Third Series, 10: 304–320, doi:10.1112/plms/s3-10.1.304, MR 0114774.
  6. ↑ This is the definition of peripheral cycles originally used by Tutte (1963). Seymour & Weaver (1984) use the same definition of a peripheral cycle, but with a different definition of a bridge that more closely resembles the induced-cycle definition for peripheral cycles.
  7. ↑ See e.g. Theorem 2.4 of Tutte (1960), showing that the vertex sets of bridges are path-connected, see Seymour & Weaver (1984) for a definition of bridges using chords and connected components, and also see Di Battista et al. (1998) for a definition of bridges using equivalence classes of the binary relation on edges.
  8. ↑ Tutte (1963), Theorems 2.7 and 2.8.
  9. ↑ See the remarks following Theorem 2.8 in Tutte (1963). As Tutte observes, this was already known to Whitney, Hassler (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society, 34 (2): 339–362, doi:10.2307/1989545, JSTOR 1989545, MR 1501641.
  10. ↑ Tutte (1963), Theorem 2.5.
  11. ↑ Bruhn, Henning (2004), "The cycle space of a 3-connected locally finite graph is generated by its finite and infinite peripheral circuits", Journal of Combinatorial Theory, Series B, 92 (2): 235–256, doi:10.1016/j.jctb.2004.03.005, MR 2099143.
  12. ↑ Thomassen, Carsten; Toft, Bjarne (1981), "Non-separating induced cycles in graphs", Journal of Combinatorial Theory, Series B, 31 (2): 199–224, doi:10.1016/S0095-8956(81)80025-1, MR 0630983.
  13. ↑ Schmidt, Jens M. (2014), "The Mondshein Sequence", Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14), Lecture Notes in Computer Science, vol. 8572, pp. 967–978, doi:10.1007/978-3-662-43948-7_80, ISBN 978-3-662-43947-0.
  14. ↑ Di Battista et al. (1998), Lemma 3.4, pp. 75–76.
  15. ↑ Seymour, P. D.; Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory, 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR 0742878.
  16. ↑ E.g. see Borse, Y. M.; Waphare, B. N. (2008), "Vertex disjoint non-separating cycles in graphs", The Journal of the Indian Mathematical Society, New Series, 75 (1–4): 75–92 (2009), MR 2662989.
  17. ↑ E.g. see Cabello, Sergio; Mohar, Bojan (2007), "Finding shortest non-separating and non-contractible cycles for topologically embedded graphs", Discrete and Computational Geometry, 37 (2): 213–235, doi:10.1007/s00454-006-1292-5, MR 2295054.
  18. ↑ Maia, Bráulio, Junior; Lemos, Manoel; Melo, Tereza R. B. (2007), "Non-separating circuits and cocircuits in matroids", Combinatorics, complexity, and chance, Oxford Lecture Ser. Math. Appl., vol. 34, Oxford: Oxford Univ. Press, pp. 162–171, doi:10.1093/acprof:oso/9780198571278.003.0010, MR 2314567{{citation}}: CS1 maint: multiple names: authors list (link).
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=परिधीय_चक्र&oldid=151696’