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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

कलन विधि

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

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

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

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

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

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

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

उपक्रांतिक $p<(1-\varepsilon )/n$: इस श्रेणी में $p$ , सभी घटक सरल और बहुत छोटे हैं। सबसे बड़े घटक का लघुगणकीय आकार है। ग्राफ़ एक छद्मवन है। इसके अधिकांश घटक ट्री हैं: चक्र वाले घटकों में शीर्षों की संख्या शीर्षों की संख्या के किसी भी असीमित कार्य की तुलना में अधिक धीमी गति से बढ़ती है। निश्चित आकार का प्रत्येक वृक्ष कई बार रैखिक रूप से होता है।^[29]
समीक्षात्मक $p\approx 1/n$: सबसे बड़े संबद्ध घटक में आनुपातिक रूप से कई शीर्ष $n^{2/3}$ .होते हैं कई अन्य बड़े घटक उपस्थित हो सकते हैं; हालाँकि, गैर-वृक्ष घटकों में शीर्षों की कुल संख्या फिर से आनुपातिक $n^{2/3}$ .^[30] है।
अतिक्रांतिक $p>(1+\varepsilon )/n$: एकल विशाल घटक है जिसमें शीर्षों की रैखिक संख्या होती है। के बड़े मूल्यों के लिए $p$ इसका आकार पूरे ग्राफ़ के निकट पहुंचता है: $|C_{1}|\approx yn$ जहाँ $y$ समीकरण $e^{-pny}=1-y$ .का धनात्मक समाधान है ,शेष घटक लघुगणकीय आकार के साथ छोटे हैं।^[31]

यादृच्छिक ग्राफ़ के एक ही मॉडल में, मानों की उच्च संभावना वाले कई संबद्ध घटक $p$ उपस्थित होंगे काफी ऊंची सीमा से नीचे, $p<(1-\varepsilon )(\log n)/n$ , और सीमा से ऊपर के मानों के लिए एकल संबद्ध घटक, $p>(1+\varepsilon )(\log n)/n$ . यह घटना कूपन संग्राहक की समस्या से निकटता से संबंधित है: संबद्ध होने के लिए, यादृच्छिक ग्राफ़ को प्रत्येक शीर्ष पर न्यूनतम एक किनारे पर घटना के लिए पर्याप्त किनारों की आवश्यकता होती है। अधिक सटीक रूप से, यदि यादृच्छिक किनारों को ग्राफ़ में एक-एक करके जोड़ा जाता है, तो उच्च संभावना के साथ पहला किनारा जिसका जोड़ पूरे ग्राफ़ को जोड़ता है, अंतिम पृथक शीर्ष को छूता है।^[32]

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

संदर्भ

↑ 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
↑ 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.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.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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ Bengelloun, Safwan Abdelmajid (December 1982), Aspects of Incremental Computing (PhD thesis), Yale University, p. 12, ProQuest 303248045
↑ 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
↑ 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
↑ Huang, Shang-En; Huang, Dawei; Kopelowitz, Tsvi; Pettie, Seth (2017), "Fully dynamic connectivity in $O{\bigl (}\log n(\log \log n)^{2}{\bigr )}$ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ 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
↑ Frieze & Karoński (2016), 2.3 Phase transition, pp. 39–45
↑ Frieze & Karoński (2016), 2.2 Super-critical phase, pp. 33; see especially Theorem 2.14, p. 33–39
↑ Frieze & Karoński (2016), 4.1 Connectivity, pp. 64–68
↑ 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

बाहरी संबंध

MATLAB code to find components in undirected graphs, MATLAB File Exchange.
Connected components, Steven Skiena, The Stony Brook Algorithm Repository

[1look-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

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

[tutte-betti-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

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

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

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

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

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

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

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

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

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

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

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

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

[tutte-matching-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

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

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

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

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

[bengalloun-21] Bengelloun, Safwan Abdelmajid (December 1982), Aspects of Incremental Computing (PhD thesis), Yale University, p. 12, ProQuest 303248045

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

[wulff-nilsen-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

[hhkp-24] Huang, Shang-En; Huang, Dawei; Kopelowitz, Tsvi; Pettie, Seth (2017), "Fully dynamic connectivity in $O{\bigl (}\log n(\log \log n)^{2}{\bigr )}$ 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

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

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

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

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

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

[critical-30] Frieze & Karoński (2016), 2.3 Phase transition, pp. 39–45

[supercritical-31] Frieze & Karoński (2016), 2.2 Super-critical phase, pp. 33; see especially Theorem 2.14, p. 33–39

[random-connectivity-32] Frieze & Karoński (2016), 4.1 Connectivity, pp. 64–68

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

Anonymous

Search

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

Namespaces

More

Page actions

Contents

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

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

कलन विधि

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

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

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

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

कलन विधि

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

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories