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