परिधीय चक्र

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

ग्राफ़ सिद्धांत में, एक अप्रत्यक्ष ग्राफ़ में परिधीय चक्र (या परिधीय परिपथ), सहज रूप से, चक्र (ग्राफ़ सिद्धांत) है जो ग्राफ़ के किसी भी भाग को किसी अन्य भाग से अलग नहीं करता है। परिधीय चक्र (या, जैसा कि उन्हें प्रारंभ में परिधीय बहुभुज कहा जाता था, क्योंकि टुट्टे ने चक्रों को "बहुभुज" कहा था) का अध्ययन सबसे पहले टुट्टे (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]

मेट्रॉइड्स में, गैर-पृथक परिपथ मैट्रॉइड का परिपथ है (जो कि, न्यूनतम निर्भर समूह है) जैसे कि माथेरॉइड माइनर परिपथ छोटे मैट्रोइड को छोड़ देता है जो जुड़ा (अर्थात, जिसे मेट्रॉइड्स के प्रत्यक्ष योग के रूप में नहीं लिखा जा सकता है) हुआ है।[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=152199’