This is a good article. Click here for more information.

घटक (ग्राफ़ सिद्धांत): Difference between revisions

From Vigyanwiki
Line 12: Line 12:
*कनेक्टेड ग्राफ़ में, वास्तव में एक घटक होता है: संपूर्ण ग्राफ़।{{r|thuswa}}
*कनेक्टेड ग्राफ़ में, वास्तव में एक घटक होता है: संपूर्ण ग्राफ़।{{r|thuswa}}
*वन (ग्राफ़ सिद्धांत) में, प्रत्येक घटक एक ट्री है (ग्राफ़ सिद्धांत)।{{r|bollobas}}
*वन (ग्राफ़ सिद्धांत) में, प्रत्येक घटक एक ट्री है (ग्राफ़ सिद्धांत)।{{r|bollobas}}
*क्लस्टर ग्राफ़ में, प्रत्येक घटक एक अधिकतम समूह है। इन ग्राफ़ों को मनमाने ढंग से अप्रत्यक्ष ग्राफ़ के [[सकर्मक समापन]] के रूप में उत्पादित किया जा सकता है, जिसके लिए सकर्मक समापन ढूंढना जुड़े हुए घटकों की पहचान करने के बराबर सूत्रीकरण है।{{r|mcnosh}}  
*क्लस्टर ग्राफ़ में, प्रत्येक घटक एक अधिकतम समूह है। इन ग्राफ़ों को यादृच्छिक ढंग से अप्रत्यक्ष ग्राफ़ के [[सकर्मक समापन]] के रूप में उत्पादित किया जा सकता है, जिसके लिए सकर्मक समापन ढूंढना जुड़े हुए घटकों की पहचान करने के बराबर सूत्रीकरण है।{{r|mcnosh}}  


घटकों की एक अन्य परिभाषा में ग्राफ के शीर्षों पर परिभाषित [[समतुल्य संबंध]] के समतुल्य वर्ग शामिल हैं। एक अप्रत्यक्ष ग्राफ़ में, एक शीर्ष {{nowrap|<math>v</math>}} एक शीर्ष {{nowrap|<math>u</math>}} से पहुंचा जा सकता है यदि <math>u</math> से {{nowrap|<math>v</math>,}} तक कोई रास्ता है, या समकक्ष एक पैदल दूरी है (एक पथ जो बार-बार कोने और किनारों की अनुमति देता है)। पहुंच योग्यता एक तुल्यता संबंध है, क्योंकि:
घटकों की एक अन्य परिभाषा में ग्राफ के शीर्षों पर परिभाषित [[समतुल्य संबंध]] के समतुल्य वर्ग शामिल हैं। एक अप्रत्यक्ष ग्राफ़ में, एक शीर्ष {{nowrap|<math>v</math>}} एक शीर्ष {{nowrap|<math>u</math>}} से पहुंचा जा सकता है यदि <math>u</math> से {{nowrap|<math>v</math>,}} तक कोई रास्ता है, या समकक्ष एक पैदल दूरी है (एक पथ जो बार-बार कोने और किनारों की अनुमति देता है)। पहुंच योग्यता एक तुल्यता संबंध है, क्योंकि:
Line 43: Line 43:


== यादृच्छिक ग्राफ़ में ==
== यादृच्छिक ग्राफ़ में ==
{{main|Giant component}}
{{main|विस्तीर्ण घटक}}
फ़ाइल: क्रिटिकल 1000-वर्टेक्स एर्डोस-रेनी-Gilbert graph.svg|thumb|एक एर्डोस-रेनी मॉडल | एर्डोस-रेनी-गिल्बर्ट यादृच्छिक ग्राफ जिसमें किनारे की संभावना के साथ 1000 शीर्ष हैं <math>p=1/(n-1)</math> (महत्वपूर्ण सीमा में), एक बड़ा घटक और कई छोटे घटक दिखा रहा है
 
यादृच्छिक ग्राफ़ में घटकों के आकार एक यादृच्छिक चर द्वारा दिए जाते हैं, जो बदले में, यादृच्छिक ग्राफ़ को कैसे चुना जाता है, इसके विशिष्ट मॉडल पर निर्भर करता है।
n यादृच्छिक ग्राफ़ में घटकों के आकार एक यादृच्छिक चर द्वारा दिए जाते हैं, जो बदले में, विशिष्ट मॉडल पर निर्भर करता है कि यादृच्छिक ग्राफ़ कैसे चुने जाते हैं। एर्दो-रेनी-गिल्बर्ट मॉडल का <math>G(n, p)</math> संस्करण में, पर एक ग्राफ <math>n</math> शीर्षों को प्रत्येक जोड़ी के लिए यादृच्छिक रूप से और स्वतंत्र रूप से चुनकर उत्पन्न किया जाता है कि क्या उस जोड़ी को जोड़ने वाले एक किनारे को शामिल किया जाए, एक किनारे को शामिल करने की संभावना {{nowrap|<math>p</math>}} और उन दो शीर्षों को जोड़ने वाले किसी किनारे के बिना छोड़ने की संभावना <math>1-p</math> के साथ।{{r|frikar}} इस मॉडल की कनेक्टिविटी {{nowrap|<math>p</math>,}} पर निर्भर करती है, और {{nowrap|<math>p</math>}} की तीन अलग-अलग श्रेणियाँ हैं जिनका व्यवहार एक दूसरे से बहुत भिन्न है। नीचे दिए गए विश्लेषण में, सभी परिणाम उच्च संभावना के साथ होते हैं, जिसका अर्थ है कि परिणाम की संभावना <math>n</math> के पर्याप्त बड़े मूल्यों के लिए यादृच्छिक ढंग से एक के करीब है। विश्लेषण एक पैरामीटर <math>\varepsilon</math> वेरेप्सिलॉन पर निर्भर करता है, {{nowrap|<math>n</math>.}} से स्वतंत्र एक सकारात्मक स्थिरांक जो यादृच्छिक ढंग से शून्य के करीब हो सकता है।
में <math>G(n, p)</math> एर्डोस-रेनी मॉडल का संस्करण|एर्डोस-रेनी-गिल्बर्ट मॉडल, पर एक ग्राफ <math>n</math> शीर्षों की प्रत्येक जोड़ी के लिए बेतरतीब ढंग से और स्वतंत्र रूप से चयन करके शीर्ष उत्पन्न किया जाता है कि क्या उस जोड़ी को जोड़ने वाले किनारे को शामिल किया जाए {{nowrap|probability <math>p</math>}} बढ़त और संभाव्यता को शामिल करने का <math>1-p</math> उन दो शीर्षों को जोड़ने वाले किसी किनारे के बिना छोड़ देना।{{r|frikar}}इस मॉडल की कनेक्टिविटी निर्भर करती है {{nowrap|on <math>p</math>,}} और तीन अलग-अलग श्रेणियां हैं {{nowrap|of <math>p</math>}} एक दूसरे से बहुत अलग व्यवहार के साथ। नीचे दिए गए विश्लेषण में, सभी परिणाम [[उच्च संभावना के साथ]] होते हैं, जिसका अर्थ है कि परिणाम की संभावना पर्याप्त रूप से बड़े मूल्यों के लिए मनमाने ढंग से एक के करीब है {{nowrap|of <math>n</math>.}} विश्लेषण एक पैरामीटर पर निर्भर करता है <math>\varepsilon</math>, से स्वतंत्र एक सकारात्मक स्थिरांक <math>n</math> वह मनमाने ढंग से शून्य के करीब हो सकता है।


;सबक्रिटिकल <math>p < (1-\varepsilon)/n</math>
;सबक्रिटिकल <math>p < (1-\varepsilon)/n</math>

Revision as of 09:06, 11 July 2023

तीन घटकों वाला एक ग्राफ़

ग्राफ़ सिद्धांत में, अप्रत्यक्ष ग्राफ़ का एक घटक एक संबद्ध सबग्राफ़ होता है जो किसी भी बड़े संबद्ध सबग्राफ़ का हिस्सा नहीं होता है। किसी भी ग्राफ के घटक उसके शीर्षों को असंयुक्त सेटों में विभाजित करते हैं, और उन सेटों के प्रेरित उपग्राफ होते हैं। एक ग्राफ जो स्वयं संबद्ध है, उसमें बिल्कुल एक घटक होता है, जिसमें पूरा ग्राफ शामिल होता है। घटकों को कभी-कभी संबद्ध घटक कहा जाता है।

किसी दिए गए ग्राफ़ में घटकों की संख्या एक महत्वपूर्ण ग्राफ़ अपरिवर्तनीय है और यह मैट्रोइड्स, टोपोलॉजिकल स्पेस और आव्यूह के अपरिवर्तनीयों से निकटता से संबंधित है। यादृच्छिक ग्राफ़ में, अक्सर होने वाली घटना एक विशाल घटक की घटना है, एक घटक जो अन्य की तुलना में काफी बड़ा है; और अंतःस्राव सीमा की, एक किनारे की संभावना जिसके ऊपर एक विशाल घटक मौजूद है और जिसके नीचे यह नहीं है।

एक ग्राफ के घटकों का निर्माण रैखिक समय में किया जा सकता है, और समस्या का एक विशेष मामला, संबद्ध घटक लेबलिंग, छवि विश्लेषण में एक बुनियादी तकनीक है। गतिशील संयोजकता एल्गोरिदम घटकों को बनाए रखते हैं क्योंकि किनारों को प्रति परिवर्तन कम समय में ग्राफ़ में डाला या हटाया जाता है। कम्प्यूटेशनल जटिलता सिद्धांत में, जुड़े हुए घटकों का उपयोग सीमित स्थान जटिलता के साथ एल्गोरिदम का अध्ययन करने के लिए किया गया है, और सबलाइनियर समय एल्गोरिदम घटकों की संख्या का सटीक अनुमान लगा सकते हैं।

परिभाषाएँ और उदाहरण

सात घटकों वाला एक क्लस्टर ग्राफ़

किसी दिए गए अप्रत्यक्ष ग्राफ़ के एक घटक को एक कनेक्टेड सबग्राफ़ के रूप में परिभाषित किया जा सकता है जो कि किसी भी बड़े कनेक्टेड सबग्राफ़ का हिस्सा नहीं है। उदाहरण के लिए, पहले उदाहरण में दिखाए गए ग्राफ़ में तीन घटक हैं। ग्राफ का प्रत्येक शीर्ष ग्राफ के घटकों में से एक से संबंधित होता है, जिसे .[1] से पहुंच योग्य शीर्षों के सेट के प्रेरित उपग्राफ के रूप में पाया जा सकता है। प्रत्येक ग्राफ़ उसके घटकों का असंयुक्त संघ है।[2] अतिरिक्त उदाहरणों में निम्न विशेष मामले शामिल हैं:

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

घटकों की एक अन्य परिभाषा में ग्राफ के शीर्षों पर परिभाषित समतुल्य संबंध के समतुल्य वर्ग शामिल हैं। एक अप्रत्यक्ष ग्राफ़ में, एक शीर्ष एक शीर्ष से पहुंचा जा सकता है यदि से , तक कोई रास्ता है, या समकक्ष एक पैदल दूरी है (एक पथ जो बार-बार कोने और किनारों की अनुमति देता है)। पहुंच योग्यता एक तुल्यता संबंध है, क्योंकि:

  • यह प्रतिवर्ती है: किसी भी शीर्ष से स्वयं तक लंबाई शून्य का एक तुच्छ पथ है।
  • यह सममित है: यदि से , तक कोई पथ है, तो विपरीत क्रम में समान किनारे से . तक पथ बनाते हैं।
  • यह सकर्मक है: यदि से तक एक पथ है और से , तक एक पथ है, तो दोनों पथों को एक साथ जोड़कर से . तक एक रास्ता बनाया जा सकता है।

इस संबंध के तुल्यता वर्ग ग्राफ़ के शीर्षों को असंयुक्त सेटों में विभाजित करते हैं, शीर्षों के उपसमुच्चय जो सभी एक दूसरे से पहुंच योग्य होते हैं, इनमें से किसी भी उपसमुच्चय के बाहर कोई अतिरिक्त पहुंच योग्य जोड़े नहीं होते हैं। प्रत्येक शीर्ष ठीक एक समतुल्य वर्ग से संबंधित है। घटक फिर इनमें से प्रत्येक तुल्यता वर्ग द्वारा गठित प्रेरित उपग्राफ होते हैं।[7] वैकल्पिक रूप से, कुछ स्रोत घटकों को उनके द्वारा प्रेरित उपग्राफ के बजाय शीर्षों के सेट के रूप में परिभाषित करते हैं।[8]

समतुल्य वर्गों से जुड़ी समान परिभाषाओं का उपयोग ग्राफ संयोजकता के अन्य रूपों के लिए परिभाषित घटकों के लिए किया गया है, जिसमें कमजोर घटक [9] और निर्देशित ग्राफ के दृढ़ता से जुड़े घटक [10] और अप्रत्यक्ष ग्राफ के द्विसंबद्ध घटक शामिल हैं।[11]

घटकों की संख्या

किसी दिए गए परिमित ग्राफ के घटकों की संख्या का उपयोग उसके फैले हुए वनों में किनारों की संख्या की गणना करने के लिए किया जा सकता है: कोने और घटकों वाले ग्राफ में, प्रत्येक फैले हुए जंगल में बिल्कुल किनारे होंगे। यह संख्या ग्राफ़ की मैट्रोइड-सैद्धांतिक रैंक और इसके ग्राफ़िक मैट्रोइड की रैंक है। दोहरे ग्राफ़िक्स मैट्रोइड की रैंक ग्राफ़ की सर्किट रैंक के बराबर होती है, किनारों की न्यूनतम संख्या जिसे ग्राफ़ के सभी चक्रों को तोड़ने के लिए हटाया जाना चाहिए। किनारों, शीर्षों और घटकों के साथ एक ग्राफ, सर्किट रैंक .[12] है।

एक ग्राफ़ की व्याख्या एक टोपोलॉजिकल स्पेस के रूप में कई तरीकों से की जा सकती है, उदाहरण के लिए इसके शीर्षों को त्रि-आयामी यूक्लिडियन स्थान में सामान्य स्थिति में बिंदुओं के रूप में रखकर और इसके किनारों को उन बिंदुओं के बीच रेखा खंडों के रूप में दर्शाया जाता है।[13] ग्राफ़ के घटकों को इन व्याख्याओं के माध्यम से संबंधित स्थान के कनेक्टेड घटक (टोपोलॉजी) के रूप में सामान्यीकृत किया जा सकता है; ये बिंदुओं के समतुल्य वर्ग हैं जिन्हें असंयुक्त बंद सेटों के जोड़े द्वारा अलग नहीं किया जा सकता है। जिस तरह एक टोपोलॉजिकल स्पेस के जुड़े घटकों की संख्या एक महत्वपूर्ण टोपोलॉजिकल अपरिवर्तनीय है, शून्य बेट्टी संख्या, एक ग्राफ के घटकों की संख्या एक महत्वपूर्ण ग्राफ अपरिवर्तनीय है, और टोपोलॉजिकल ग्राफ सिद्धांत में इसकी व्याख्या ग्राफ़ के शून्यवें बेट्टी नंबर के रूप में की जा सकती है।[3]

ग्राफ सिद्धांत में घटकों की संख्या अन्य तरीकों से भी सामने आती है। बीजगणितीय ग्राफ सिद्धांत में यह एक परिमित ग्राफ़ के लाप्लासियन आव्यूह के आइगेनवैल्यू के रूप में 0 की बहुलता के बराबर है।[14] यह ग्राफ़ के वर्णिक बहुपद के पहले गैर-शून्य गुणांक का सूचकांक भी है, और पूरे ग्राफ़ का वर्णिक बहुपद इसके घटकों के बहुपद के उत्पाद के रूप में प्राप्त किया जा सकता है।[15] पूर्ण मिलान वाले परिमित ग्राफ़ को चित्रित करने वाले टुट्टे प्रमेय में घटकों की संख्या एक महत्वपूर्ण भूमिका निभाती है[16] और अधिकतम मिलान के आकार के लिए संबंधित टुटे-बर्ज सूत्र,[17] और ग्राफ़ की कठोरता की परिभाषा में है।[18]

एल्गोरिदम

चौड़ाई-पहली खोज या गहराई-पहली खोज का उपयोग करके रैखिक समय में (ग्राफ के शीर्षों और किनारों की संख्या के संदर्भ में) एक परिमित ग्राफ के घटकों की गणना करना सरल है। किसी भी स्थिति में, एक खोज जो किसी विशेष शीर्ष पर शुरू होती है, वापस लौटने से पहले (और नहीं) वाले पूरे घटक को ढूंढ लेगी। किसी ग्राफ़ के सभी घटकों को उसके शीर्षों के माध्यम से लूपिंग करके पाया जा सकता है, जब भी लूप किसी ऐसे शीर्ष पर पहुंचता है जो पहले से पाए गए घटक में शामिल नहीं किया गया है, तो एक नई चौड़ाई-पहली या गहराई-पहली खोज शुरू की जा सकती है। हॉपक्रॉफ्ट और टार्जन (1973) मूलतः इस एल्गोरिथम का वर्णन करते हैं, और बताते हैं कि यह पहले से ही "अच्छी तरह से ज्ञात" था।[19]

कनेक्टेड-घटक लेबलिंग, कंप्यूटर छवि विश्लेषण में एक बुनियादी तकनीक, छवि से एक ग्राफ का निर्माण और ग्राफ पर घटक विश्लेषण शामिल है। शीर्ष छवि के पिक्सेल का सबसेट हैं, जिन्हें रुचिकर या चित्रित वस्तुओं का हिस्सा होने की संभावना के रूप में चुना जाता है। किनारे पिक्सेल कनेक्टिविटी को जोड़ते हैं, वॉन न्यूमैन प्रतिवैस के अनुसार आसन्नता को या तो ऑर्थोगोनल रूप से परिभाषित किया जाता है, या मूर प्रतिवैस के अनुसार ऑर्थोगोनल और तिरछे दोनों तरह से परिभाषित किया जाता है। इस ग्राफ़ के संबद्ध घटकों की पहचान करने से अतिरिक्त प्रसंस्करण को छवि के उन हिस्सों में अधिक संरचना ढूंढने या यह पहचानने की अनुमति मिलती है कि किस प्रकार की वस्तु को दर्शाया गया है। शोधकर्ताओं ने इस प्रकार के ग्राफ़ के लिए विशिष्ट घटक-खोज एल्गोरिदम विकसित किए हैं, जो इसे अधिक बिखरे हुए क्रम के बजाय पिक्सेल क्रम में संसाधित करने की अनुमति देता है जो कि चौड़ाई-पहले या गहराई-पहले खोज द्वारा उत्पन्न होगा। यह उन स्थितियों में उपयोगी हो सकता है जहां पिक्सेल तक अनुक्रमिक पहुंच यादृच्छिक पहुंच से अधिक कुशल होती है, या तो क्योंकि छवि को पदानुक्रमित तरीके से दर्शाया जाता है जो तेज़ यादृच्छिक पहुंच की अनुमति नहीं देता है या क्योंकि अनुक्रमिक पहुंच बेहतर मेमोरी एक्सेस पैटर्न उत्पन्न करती है।[20]

शीर्षों और किनारों को जोड़े जाने पर ग्राफ़ के घटकों को गतिशील रूप से ट्रैक करने के लिए कुशल एल्गोरिदम भी हैं, एक असंयुक्त-सेट डेटा संरचना का उपयोग करके समतुल्य वर्गों में शीर्षों के विभाजन का ट्रैक रखने के लिए, किन्हीं दो वर्गों को उनके संघ द्वारा प्रतिस्थापित किया जाता है जब एक उन्हें जोड़ने वाला किनारा जोड़ा गया है। ये एल्गोरिदम परिशोधित विश्लेषण समय लेते हैं प्रति ऑपरेशन, जहां शीर्ष और किनारों को जोड़ना और उस घटक का निर्धारण करना जिसमें शीर्ष गिरता है, दोनों ऑपरेशन हैं, और बहुत तेजी से बढ़ने वाले एकरमैन फ़ंक्शन का बहुत धीरे-धीरे बढ़ने वाला उलटा है।[21] इस प्रकार के वृद्धिशील कनेक्टिविटी एल्गोरिदम का एक अनुप्रयोग न्यूनतम फैले हुए पेड़ों के लिए क्रुस्कल के एल्गोरिदम में है, जो लंबाई के अनुसार क्रमबद्ध क्रम में ग्राफ़ में किनारों को जोड़ता है और न्यूनतम फैले हुए ट्री में एक किनारे को तभी शामिल करता है जब यह पहले के दो अलग-अलग घटकों को जोड़ता है- सबग्राफ जोड़ा गया।[22] जब किनारे सम्मिलन और किनारे विलोपन दोनों की अनुमति होती है, तो गतिशील कनेक्टिविटी एल्गोरिदम अभी भी उसी जानकारी को परिशोधित समय में बनाए रख सकते हैं प्रति परिवर्तन और समय प्रति कनेक्टिविटी क्वेरी,[23] या निकट-लघुगणक यादृच्छिक यादृच्छिक अपेक्षित समय में।[24]

ट्यूरिंग मशीनों की शक्ति का अध्ययन करने के लिए ग्राफ़ के घटकों का उपयोग कम्प्यूटेशनल जटिलता सिद्धांत में किया गया है, जिनकी कार्यशील मेमोरी बिट्स की लॉगरिदमिक संख्या तक सीमित है, जिसमें बहुत बड़ा इनपुट परिवर्तनीय होने के बजाय केवल पढ़ने की पहुंच के माध्यम से पहुंच योग्य है। इस तरह से सीमित मशीनों द्वारा हल की जा सकने वाली समस्याएं जटिलता वर्ग एल को परिभाषित करती हैं। यह कई वर्षों तक अस्पष्ट था कि क्या इस मॉडल में जुड़े हुए घटक पाए जा सकते हैं, जब परीक्षण की निर्णय समस्या के रूप में औपचारिक रूप दिया गया कि क्या दो कोने एक ही घटक से संबंधित हैं, और 1982 में एक संबंधित जटिलता वर्ग, एसएल, को इस कनेक्टिविटी समस्या और इसके समतुल्य किसी भी अन्य समस्या को लॉगरिदमिक-स्पेस कटौती के तहत शामिल करने के लिए परिभाषित किया गया था।[25] 2008 में अंततः यह सिद्ध हो गया कि इस कनेक्टिविटी समस्या को लॉगरिदमिक स्पेस में हल किया जा सकता है, और इसलिए SL = LSL = L.[26]।

आसन्न सूची के रूप में दर्शाए गए ग्राफ़ में, इसके शीर्षों तक यादृच्छिक पहुंच के साथ, जुड़े हुए घटकों की संख्या का अनुमान लगाना संभव है, सबलाइनर समय में, अधिकांश पर एडिटिव (पूर्ण) त्रुटि प्राप्त करने की निरंतर संभावना के साथ है।[27]

यादृच्छिक ग्राफ़ में

Main article: विस्तीर्ण घटक

n यादृच्छिक ग्राफ़ में घटकों के आकार एक यादृच्छिक चर द्वारा दिए जाते हैं, जो बदले में, विशिष्ट मॉडल पर निर्भर करता है कि यादृच्छिक ग्राफ़ कैसे चुने जाते हैं। एर्दो-रेनी-गिल्बर्ट मॉडल का संस्करण में, पर एक ग्राफ शीर्षों को प्रत्येक जोड़ी के लिए यादृच्छिक रूप से और स्वतंत्र रूप से चुनकर उत्पन्न किया जाता है कि क्या उस जोड़ी को जोड़ने वाले एक किनारे को शामिल किया जाए, एक किनारे को शामिल करने की संभावना और उन दो शीर्षों को जोड़ने वाले किसी किनारे के बिना छोड़ने की संभावना के साथ।[28] इस मॉडल की कनेक्टिविटी , पर निर्भर करती है, और की तीन अलग-अलग श्रेणियाँ हैं जिनका व्यवहार एक दूसरे से बहुत भिन्न है। नीचे दिए गए विश्लेषण में, सभी परिणाम उच्च संभावना के साथ होते हैं, जिसका अर्थ है कि परिणाम की संभावना के पर्याप्त बड़े मूल्यों के लिए यादृच्छिक ढंग से एक के करीब है। विश्लेषण एक पैरामीटर वेरेप्सिलॉन पर निर्भर करता है, . से स्वतंत्र एक सकारात्मक स्थिरांक जो यादृच्छिक ढंग से शून्य के करीब हो सकता है।

सबक्रिटिकल
इस श्रेणी में , सभी घटक सरल और बहुत छोटे हैं। सबसे बड़े घटक का लघुगणकीय आकार है। ग्राफ़ एक छद्म वन है. इसके अधिकांश घटक ट्री हैं: चक्र वाले घटकों में शीर्षों की संख्या शीर्षों की संख्या के किसी भी असीमित कार्य की तुलना में अधिक धीमी गति से बढ़ती है। निश्चित आकार का प्रत्येक वृक्ष कई बार रैखिक रूप से होता है।[29]
गंभीर
सबसे बड़े संबद्ध घटक में आनुपातिक रूप से कई शीर्ष होते हैं . कई अन्य बड़े घटक मौजूद हो सकते हैं; हालाँकि, गैर-वृक्ष घटकों में शीर्षों की कुल संख्या फिर से आनुपातिक है .[30]
सुपरक्रिटिकल
एक एकल विशाल घटक है जिसमें शीर्षों की एक रैखिक संख्या होती है। के बड़े मूल्यों के लिए इसका आकार पूरे ग्राफ़ के करीब पहुंचता है: कहाँ समीकरण का सकारात्मक समाधान है . शेष घटक लघुगणकीय आकार के साथ छोटे हैं।[31]

यादृच्छिक ग्राफ़ के एक ही मॉडल में, मानों की उच्च संभावना वाले कई संबद्ध घटक मौजूद होंगे काफी ऊंची सीमा से नीचे, , और सीमा से ऊपर के मानों के लिए एक एकल संबद्ध घटक, . यह घटना कूपन संग्राहक की समस्या से निकटता से संबंधित है: कनेक्ट होने के लिए, एक यादृच्छिक ग्राफ़ को प्रत्येक शीर्ष पर कम से कम एक किनारे पर घटना के लिए पर्याप्त किनारों की आवश्यकता होती है। अधिक सटीक रूप से, यदि यादृच्छिक किनारों को ग्राफ़ में एक-एक करके जोड़ा जाता है, तो उच्च संभावना के साथ पहला किनारा जिसका जोड़ पूरे ग्राफ़ को जोड़ता है, अंतिम पृथक शीर्ष को छूता है।[32]

ग्रिड ग्राफ़ के यादृच्छिक उपग्राफ सहित विभिन्न मॉडलों के लिए, संबद्ध घटकों को परकोलेशन सिद्धांत द्वारा वर्णित किया गया है। इस सिद्धांत में एक महत्वपूर्ण प्रश्न एक परकोलेशन थ्रेशोल्ड का अस्तित्व है, एक महत्वपूर्ण संभावना जिसके ऊपर एक विशाल घटक (या अनंत घटक) मौजूद है और जिसके नीचे यह नहीं है।[33]

संदर्भ

  1. ↑ Clark, John; Holton, Derek Allan (1995), A First Look at Graph Theory, Allied Publishers, p. 28, ISBN 9788170234630, archived from the original on 2022-01-08, retrieved 2022-01-07
  2. ↑ Joyner, David; Nguyen, Minh Van; Phillips, David (May 10, 2013), "1.6.1 Union, intersection, and join", Algorithmic Graph Theory and Sage (0.8-r1991 ed.), Google, pp. 34–35, archived from the original on January 16, 2016, retrieved January 8, 2022
  3. ↑ 3.0 3.1 Tutte, W. T. (1984), Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 21, Reading, Massachusetts: Addison-Wesley, p. 15, ISBN 0-201-13520-5, MR 0746795, archived from the original on 2022-01-07, retrieved 2022-01-07
  4. ↑ 4.0 4.1 Thulasiraman, K.; Swamy, M. N. S. (2011), Graphs: Theory and Algorithms, John Wiley & Sons, p. 9, ISBN 978-1-118-03025-7, archived from the original on 2022-01-07, retrieved 2022-01-07
  5. ↑ Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, New York: Springer-Verlag, p. 6, doi:10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, MR 1633290, archived from the original on 2022-01-08, retrieved 2022-01-08
  6. ↑ McColl, W. F.; Noshita, K. (1986), "On the number of edges in the transitive closure of a graph", Discrete Applied Mathematics, 15 (1): 67–73, doi:10.1016/0166-218X(86)90020-X, MR 0856101
  7. ↑ Foldes, Stephan (2011), Fundamental Structures of Algebra and Discrete Mathematics, John Wiley & Sons, p. 199, ISBN 978-1-118-03143-8, archived from the original on 2022-01-07, retrieved 2022-01-07
  8. ↑ Siek, Jeremy; Lee, Lie-Quan; Lumsdaine, Andrew (2001), "7.1 Connected components: Definitions", The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley, pp. 97–98
  9. ↑ Knuth, Donald E. (January 15, 2022), "Weak components", The Art of Computer Programming, Volume 4, Pre-Fascicle 12A: Components and Traversal (PDF), pp. 11–14, archived (PDF) from the original on January 18, 2022, retrieved March 1, 2022
  10. ↑ Lewis, Harry; Zax, Rachel (2019), Essential Discrete Mathematics for Computer Science, Princeton University Press, p. 145, ISBN 978-0-691-19061-7, archived from the original on 2022-01-08, retrieved 2022-01-08
  11. ↑ Kozen, Dexter C. (1992), "4.1 Biconnected components", The Design and Analysis of Algorithms, Texts and Monographs in Computer Science, New York: Springer-Verlag, pp. 20–22, doi:10.1007/978-1-4612-4400-4, ISBN 0-387-97687-6, MR 1139767, S2CID 27747202, archived from the original on 2022-01-08, retrieved 2022-01-08
  12. ↑ Wilson, R. J. (1973), "An introduction to matroid theory", The American Mathematical Monthly, 80 (5): 500–525, doi:10.1080/00029890.1973.11993318, JSTOR 2319608, MR 0371694
  13. ↑ Wood, David R. (2014), "Three-dimensional graph drawing", in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms (PDF), Springer, pp. 1–7, doi:10.1007/978-3-642-27848-8_656-1, archived (PDF) from the original on 2022-01-08, retrieved 2022-01-08
  14. ↑ Cioabă, Sebastian M. (2011), "Some applications of eigenvalues of graphs", in Dehmer, Matthias (ed.), Structural Analysis of Complex Networks, New York: Birkhäuser/Springer, pp. 357–379, doi:10.1007/978-0-8176-4789-6_14, MR 2777924; see proof of Lemma 5, p. 361 Archived 2022-01-08 at the Wayback Machine
  15. ↑ Read, Ronald C. (1968), "An introduction to chromatic polynomials", Journal of Combinatorial Theory, 4: 52–71, doi:10.1016/S0021-9800(68)80087-0, MR 0224505; see Theorem 2, p. 59, and corollary, p. 65
  16. ↑ Tutte, W. T. (1947), "The factorization of linear graphs", The Journal of the London Mathematical Society, 22 (2): 107–111, doi:10.1112/jlms/s1-22.2.107, MR 0023048
  17. ↑ Berge, Claude (1958), "Sur le couplage maximum d'un graphe", Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, 247: 258–259, MR 0100850
  18. ↑ Chvátal, Václav (1973), "Tough graphs and Hamiltonian circuits", Discrete Mathematics, 5 (3): 215–228, doi:10.1016/0012-365X(73)90138-6, MR 0316301
  19. ↑ Hopcroft, John; Tarjan, Robert (June 1973), "Algorithm 447: efficient algorithms for graph manipulation", Communications of the ACM, 16 (6): 372–378, doi:10.1145/362248.362272, S2CID 14772567
  20. ↑ Dillencourt, Michael B.; Samet, Hanan; Tamminen, Markku (1992), "A general approach to connected-component labeling for arbitrary image representations", Journal of the ACM, 39 (2): 253–280, doi:10.1145/128749.128750, MR 1160258, S2CID 1869184
  21. ↑ Bengelloun, Safwan Abdelmajid (December 1982), Aspects of Incremental Computing (PhD thesis), Yale University, p. 12, ProQuest 303248045
  22. ↑ Skiena, Steven (2008), "6.1.2 Kruskal's Algorithm", The Algorithm Design Manual, Springer, pp. 196–198, Bibcode:2008adm..book.....S, doi:10.1007/978-1-84800-070-4, ISBN 978-1-84800-069-8, archived from the original on 2022-01-07, retrieved 2022-01-07
  23. ↑ Wulff-Nilsen, Christian (2013), "Faster deterministic fully-dynamic graph connectivity", in Khanna, Sanjeev (ed.), Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pp. 1757–1769, arXiv:1209.5608, doi:10.1137/1.9781611973105.126, S2CID 13397958
  24. ↑ Huang, Shang-En; Huang, Dawei; Kopelowitz, Tsvi; Pettie, Seth (2017), "Fully dynamic connectivity in amortized expected time", in Klein, Philip N. (ed.), Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 510–520, arXiv:1609.05867, doi:10.1137/1.9781611974782.32, S2CID 15585534
  25. ↑ Lewis, Harry R.; Papadimitriou, Christos H. (1982), "Symmetric space-bounded computation", Theoretical Computer Science, 19 (2): 161–187, doi:10.1016/0304-3975(82)90058-5, MR 0666539
  26. ↑ Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): A17:1–A17:24, doi:10.1145/1391289.1391291, MR 2445014
  27. ↑ Berenbrink, Petra; Krayenhoff, Bruce; Mallmann-Trenn, Frederik (2014), "Estimating the number of connected components in sublinear time", Information Processing Letters, 114 (11): 639–642, doi:10.1016/j.ipl.2014.05.008, MR 3230913
  28. ↑ Frieze, Alan; Karoński, Michał (2016), "1.1 Models and relationships", Introduction to Random Graphs, Cambridge University Press, Cambridge, pp. 3–9, doi:10.1017/CBO9781316339831, ISBN 978-1-107-11850-8, MR 3675279
  29. ↑ Frieze & Karoński (2016), 2.1 Sub-critical phase, pp. 20–33; see especially Theorem 2.8, p. 26, Theorem 2.9, p. 28, and Lemma 2.11, p. 29
  30. ↑ Frieze & Karoński (2016), 2.3 Phase transition, pp. 39–45
  31. ↑ Frieze & Karoński (2016), 2.2 Super-critical phase, pp. 33; see especially Theorem 2.14, p. 33–39
  32. ↑ Frieze & Karoński (2016), 4.1 Connectivity, pp. 64–68
  33. ↑ Cohen, Reuven; Havlin, Shlomo (2010), "10.1 Percolation on complex networks: Introduction", Complex Networks: Structure, Robustness and Function, Cambridge University Press, pp. 97–98, ISBN 978-1-139-48927-0, archived from the original on 2022-01-10, retrieved 2022-01-10


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=घटक_(ग्राफ़_सिद्धांत)&oldid=220683’