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

Revision as of 06:54, 29 April 2023

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

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

परिभाषाएँ

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

$C$ परिधीय है यदि यह गुण के साथ जुड़े ग्राफ़ में साधारण चक्र है, जो कि $G\setminus C$ में प्रत्येक दो किनारों $e_{1}$ और $e_{2}$ के लिए $G$ में एक पथ उपस्थित है, और इसी $e_{2}$ के साथ समाप्त होता है, और $C$ से संबंधित कोई आंतरिक शीर्ष नहीं है।^[2]
$C$ परिधीय है यदि यह संपत्ति के साथ एक प्रेरित चक्र है जो कि $C$ के किनारों और कोने को हटाकर गठित उपग्राफ $G\setminus C$ जुड़ा हुआ है।^[3]
यदि $C$ , $G$ का कोई सबग्राफ है, तो $C$ का एक सेतु^[4] $G$ का एक न्यूनतम सबग्राफ $B$ है जो कि $C$ से एज-डिसजॉइंट है और उसके पास वह गुण है जो उसके संलग्नक के सभी बिंदु ( $B$ और $G\setminus B$ दोनों में किनारों से सटे शीर्ष) C से संबंधित हैं।^[5] एक साधारण चक्र $C$ परिधीय है यदि इसमें ठीक सेतु है।^[6]

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

गुण

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

संदर्भ

↑ 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 $G$ has isolated vertices from disconnections caused by the removal of $C$ .
↑ Not to be confused with bridge (graph theory), a different concept.
↑ 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.
↑ 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.
↑ 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.
↑ Tutte (1963), Theorems 2.7 and 2.8.
↑ 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.
↑ Tutte (1963), Theorem 2.5.
↑ 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.
↑ 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.
↑ 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.
↑ Di Battista et al. (1998), Lemma 3.4, pp. 75–76.
↑ 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.
↑ 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.
↑ 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.
↑ 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).

[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.

[dett-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 $G$ has isolated vertices from disconnections caused by the removal of $C$ .

[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).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

@@ Line 1: / Line 1: @@
 {{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|टुट्टे|1963}} द्वारा किया गया था और वे [[ प्लेनर ग्राफ |प्लेनर ग्राफ़]] के लक्षण वर्णन में और गैर-प्लानर ग्राफ़ के [[चक्र स्थान]] बनाने में महत्वपूर्ण भूमिका निभाते हैं।<ref>{{citation
+[[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
   | journal = Proceedings of the London Mathematical Society
@@ Line 84: / Line 84: @@
   | isbn = 978-3-662-43947-0
   }}.</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
   | last1 = Seymour | first1 = P. D. | author1-link = Paul Seymour (mathematician)
@@ Line 122: / Line 122: @@
   | year = 2007| doi-access = free
   }}.</ref>
-मेट्रॉइड्स में, गैर-पृथक सर्किट [[ matroid |matroid]] का सर्किट है (जो कि, न्यूनतम निर्भर सेट है) जैसे कि [[माथेरॉइड माइनर]] सर्किट छोटे मैट्रोइड को छोड़ देता है जो जुड़ा हुआ है (अर्थात, जिसे मेट्रॉइड्स के प्रत्यक्ष योग के रूप में नहीं लिखा जा सकता है) ).<ref>{{citation
+मेट्रॉइड्स में, गैर-पृथक परिपथसर्किट [[ matroid |matroid]] का परिपथसर्किट है (जो कि, न्यूनतम निर्भर सेट है) जैसे कि [[माथेरॉइड माइनर]] परिपथसर्किट छोटे मैट्रोइड को छोड़ देता है जो जुड़ा हुआ है (अर्थात, जिसे मेट्रॉइड्स के प्रत्यक्ष योग के रूप में नहीं लिखा जा सकता है) ).<ref>{{citation
   | last1 = Maia | first1 = Bráulio, Junior
   | last2 = Lemos | first2 = Manoel
@@ Line 135: / Line 135: @@
   | title = Combinatorics, complexity, and chance
   | 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> अविभाज्य है।
 ==संदर्भ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 06:54, 29 April 2023

Contents

परिभाषाएँ

गुण

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 06:54, 29 April 2023

परिभाषाएँ

गुण

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories