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

Revision as of 18:56, 28 April 2023

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

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

परिभाषाएँ

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

$C$ परिधीय है यदि यह संपत्ति के साथ जुड़े ग्राफ में साधारण चक्र है, जो हर दो किनारों के लिए है $e_{1}$ और $e_{2}$ में $G\setminus C$ , में पथ मौजूद है $G$ से शुरू होता है $e_{1}$ , इसी के साथ समाप्त होता है $e_{2}$ , और इससे संबंधित कोई आंतरिक शीर्ष नहीं है $C$ .^[2]
$C$ परिधीय है अगर यह सबग्राफ की संपत्ति के साथ प्रेरित चक्र है $G\setminus C$ के किनारों और शीर्षों को हटाकर बनाया गया है $C$ जुड़ा है।^[3]
अगर $C$ का कोई सबग्राफ है $G$ , पुल^[4] का $C$ न्यूनतम सबग्राफ है $B$ का $G$ वह किनारे से अलग है $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|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
   | 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
+परिधीय चक्र [[ बहुफलकीय ग्राफ |बहुफलकीय ग्राफ]] ़ के सिद्धांत में प्रकट होते हैं, जो कि, [[के-वर्टेक्स-कनेक्टेड ग्राफ]]़ | 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
   | doi = 10.2307/1989545
@@ Line 122: / Line 122: @@
   | year = 2007| doi-access = free
   }}.</ref>
-मेट्रॉइड्स में, गैर-पृथक सर्किट [[ matroid ]] का सर्किट है (जो कि, न्यूनतम निर्भर सेट है) जैसे कि [[माथेरॉइड माइनर]] सर्किट छोटे मैट्रोइड को छोड़ देता है जो जुड़ा हुआ है (अर्थात, जिसे मेट्रॉइड्स के प्रत्यक्ष योग के रूप में नहीं लिखा जा सकता है) ).<ref>{{citation
+मेट्रॉइड्स में, गैर-पृथक सर्किट [[ matroid |matroid]] का सर्किट है (जो कि, न्यूनतम निर्भर सेट है) जैसे कि [[माथेरॉइड माइनर]] सर्किट छोटे मैट्रोइड को छोड़ देता है जो जुड़ा हुआ है (अर्थात, जिसे मेट्रॉइड्स के प्रत्यक्ष योग के रूप में नहीं लिखा जा सकता है) ).<ref>{{citation
   | last1 = Maia | first1 = Bráulio, Junior
   | last2 = Lemos | first2 = Manoel

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 18:56, 28 April 2023

Contents

परिभाषाएँ

गुण

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 18:56, 28 April 2023

परिभाषाएँ

गुण

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories