परिधि (ग्राफ सिद्धांत)
ग्राफ सिद्धांत में एक अप्रत्यक्ष ग्राफ का घेरा है जो ग्राफ में निहित सबसे छोटे चक्र ग्राफ सिद्धांत की लंबाई है [1] तथा ग्राफ़ में कोई चक्र भी नहीं है अर्थात यह एक ग्राफ़ सिद्धांत है इसकी परिधि को अनंत के रूप में परिभाषित किया गया है [2]उदाहरण के लिए एक 4-चक्र के वर्ग का घेरा 4 होता है तथा ग्रिड का घेरा भी 4 होता है और एक त्रिकोणीय जाल का घेरा 3 होता है जो अधिक परिधि वाले ग्राफ त्रिभुज से मुक्त होता है।
पिंजरों
घेरा का एक घनीय ग्राफ जिसके शीर्षों की डिग्री तीन है g जितना संभव हो उतना छोटा किया जा सकता है और यह a के रूप में जाना जाता है g-पिंजरा ग्राफ सिद्धांत या a ग्राफ अद्वितीय 5- पिंजरा है यह परिधि 5 का सबसे छोटा घन ग्राफ है हीवुड ग्राफ अद्वितीय 6-पिंजरा है तथा यह मैक्गी ग्राफ अद्वितीय 7-पिंजरा है और अद्वितीय 8- पिंजरा है [3] जो किसी दिए गए घेरे के लिए कई पिंजरे एकत्र हो सकते हैं उदाहरण के लिए तीन गैर-समरूपी 10-पिंजरे हैं जिनमें से प्रत्येक में 70 शिखर हैं बलबन 10 जो पिंजराहैरी ग्राफ और हैरी-वोंग ग्राफ का है।
पीटरसन ग्राफ का घेरा 5 है
हेवुड ग्राफ में 6 का घेरा है
मैक्गी ग्राफ का घेरा 7 है
टुट्टे-कॉक्सेटर ग्राफ (टुट्टे आठ पिंजरे) में 8 का घेरा है
परिधि और ग्राफ रंग
किसी भी सकारात्मक पूर्णांक के लिए g और χ कम से कम परिधि के साथ एक ग्राफ में एकत्र हैं और g रंगीन संख्या में कम से कम χ है उदाहरण के लिए ग्रोटजस्ट का ग्राफ त्रिकोण-मुक्त है और इसमें रंगीन संख्या 4 हैं और ग्रोटजस्ट ग्राफ बनाने के लिए उपयोग किए जाने वाले माईस्क्लीनकिन के निर्माण को दोहराते हुए मनमाने ढंग से बड़ी रंगीन संख्या के त्रिकोण-मुक्त रेखांकन का उत्पादन करता है संभाव्यता पद्धति का उपयोग करते हुए पॉल एर्दोस सामान्य परिणाम को सिद्ध करने वाले पहले व्यक्ति थे [4] जिसे सही रूप से उन्होंने दिखाया कि एक यादृच्छिक ग्राफ पर n शीर्ष स्वतंत्र रूप से चुनकर बनते हैं प्रत्येक किनारे को प्रायिकता के साथ सम्मिलित किया जाए तथा n(1–g)/g के रूप में 1 होने की संभावना के साथ है n अधिक से अधिक अनंत तक जाता है n⁄2 लंबाई का चक्र g या उससे कम लेकिन आकार का कोई स्वतंत्र समूह ग्राफ़ सिद्धांत नहीं है n⁄2k . इसलिए प्रत्येक छोटे चक्र से एक शीर्ष को हटाने से एक छोटा ग्राफ निकल आता है जिसकी परिधि अधिक होती है g जिसमें रंग का प्रत्येक वर्ग छोटा होना चाहिए जिसके लिए रंग की कम से कम आवश्यकता होती है k किसी भी रंग में बदला जा सकता है।
स्पष्ट यह है कि बड़े उच्च परिधि और रंगीन संख्या वाले परिमित क्षेत्रों में रैखिक समूहों को कुछ केली ग्राफ के रूप में बनाया जा सकता है [5] इन उल्लेखनीय रामानुजन रेखांकन में बड़े विस्तारक ग्राफ भी हैं।
संबंधित अवधारणाएँ
एक ग्राफ का विषम घेरा और सम घेरा है जो क्रमशः सबसे छोटे विषम चक्र और सबसे छोटे सम चक्र की लंबाई है
दृश्यमान परिधि एक ग्राफ का सबसे छोटा होने के जगह सबसे लंबे सरल चक्र की लंबाई है
एक गैर-तुच्छ चक्र को कम से कम लंबाई के रूप में सोचा गया कि परिधि प्राकृतिक सामान्यीकरण प्रकुंचन में उच्च सिकुड़न के रूप में स्वीकार करती है।
गर्थ के-एज-कनेक्टेड ग्राफ की दोहरी अवधारणा यह है कि एक समतल ग्राफ का घेरा इसके दोहरे ग्राफ की बढ़त प्रारूप है और इसके विपरीत इन अवधारणाओं को मापन विज्ञान सिद्धांत में उल्काभ परिधि द्वारा एकीकृत किया गया है मापन विज्ञान में सबसे छोटे आश्रित समूह का आकार एक लेखाचित्रीय मापन विज्ञान के लिए उल्काभि अंतर्निहित ग्राफ में परिधि के बराबर होता है जबकि सह- लेखाचित्रीय मापन विज्ञान के लिए यह उम्र के बराबर होता है।[6]
गणना
जटिलता के साथ प्रत्येक बिंदु से एक चौड़ाई की पहली खोज एक अप्रत्यक्ष ग्राफ की परिधि की गणना की जा सकती है जहाँ ग्राफ के शीर्षों की संख्या है और किनारों की संख्या है [7]यह एक व्यावहारिक अनुकूलन बीएफएस की गहराई को उस गहराई तक सीमित करता है जो अब तक खोजे गए सबसे छोटे चक्र की लंबाई पर निर्भर करता है [8] बेहतर प्रारूप उस स्थान में जाना जाता है जहां परिधि सम है[9] और जब ग्राफ समतल हो [10] निचली सीमाओं के संदर्भ में ग्राफ़ के परिधि की गणना करना कम से कम उतना ही कठिन है जितना कि ग्राफ़ पर त्रिभुज ढूँढने की समस्या को हल करना है।
संदर्भ
- ↑ R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
- ↑ Weisstein, Eric W., "Girth", MathWorld
- ↑ Brouwer, Andries E., Cages. Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
- ↑ Erdős, Paul (1959), "Graph theory and probability", Canadian Journal of Mathematics, 11: 34–38, doi:10.4153/CJM-1959-003-9, S2CID 122784453.
- ↑ Davidoff, Giuliana; Sarnak, Peter; Valette, Alain (2003), Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, vol. 55, Cambridge University Press, Cambridge, doi:10.1017/CBO9780511615825, ISBN 0-521-82426-5, MR 1989434
- ↑ Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics, 155 (18): 2456–2470, doi:10.1016/j.dam.2007.06.015, MR 2365057.
- ↑ [1]
- ↑ Völkel, Christoph Dürr, Louis Abraham and Finn (2016-11-06). "सबसे छोटा चक्र". TryAlgo (in English). Retrieved 2023-02-22.
{{cite web}}: CS1 maint: multiple names: authors list (link) - ↑ "ds.algorithms - Optimal algorithm for finding the girth of a sparse graph?". Theoretical Computer Science Stack Exchange (in English). Retrieved 2023-02-22.
- ↑ Chang, Hsien-Chih; Lu, Hsueh-I. (2013). "रेखीय समय में समतलीय ग्राफ़ की परिधि की गणना करना". SIAM Journal on Computing. 42 (3): 1077–1094. doi:10.1137/110832033. ISSN 0097-5397.
