दृढ़ता से जुड़े घटक क्या हैं?

Question

मुझे कई एल्गोरिदम मिले हैं जो को निर्देशित ग्राफ में दृढ़ता से जुड़े घटक खोजने के लिए बताते हैं, लेकिन क्यों आप यह करना चाहते हैं। दृढ़ता से जुड़े घटकों के कुछ अनुप्रयोग क्या हैं?

Answer 1

आपको टिम रफगार्डन को Coursera पर एल्गोरिदम कोर्स का परिचय देखना चाहिए। वह प्रत्येक एल्गोरिदम के लिए चला जाता है, वह इसके कुछ अनुप्रयोगों को बताता है। बहुत उपयोगी है, और एल्गोरिदम का अध्ययन करने के मूल्य को देखता है!

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

इसका उपयोग जनसंख्या के हिस्सों को देखने के लिए भी किया जा सकता है। कहो, "वाह, इस विशाल घटक में पीछे की ओर चलने का शौक है और मोल्ड पिज्जा खाने पसंद है!" यह सहसंबंध दिखा सकता है। मोल्ड पिज्जा के विज्ञापनदाता इस डेटा का उपयोग उन लोगों को लक्षित करने के लिए करेंगे जो पीछे की ओर चलना पसंद करते हैं। कौन जाने!

Answer 2

एक उदाहरण model checking में है:

प्रभावशाली तरीके से कनेक्ट घटक ढूँढना formal verification में स्पष्ट model checking में किया जाता है।

मॉडल की जाँच में - हम एक राज्य मशीन है, जो हमारे सॉफ्टवेयर/हार्डवेयर के मॉडल का प्रतिनिधित्व करता है, और हम उस पर temporal logic सूत्रों साबित करने के लिए प्रयास करें।

उदाहरण के लिए: सूत्र EG(p) साधन: वहाँ ग्राफ में एक मार्ग है, जहां प्रत्येक राज्य के लिए - तर्क सूत्र p पैदावार true।

algorithm for proving if EG(p) is true on a graph (मॉडल) अधिकतम दृढ़ता से जुड़े घटक (एससीसी) को ढूंढ रहा है, और उसके बाद ग्राफ में इसके पथों की जांच कर रहा है।

ध्यान दें कि मॉडल जांच व्यापक रूप से उद्योग में लागू होती है - खासकर हार्डवेयर घटकों की शुद्धता साबित करने के लिए।

---

(1) कंप्यूटर विज्ञान के लिए अस्थायी तर्क के महत्व महान है, और इसके आविष्कारक Amir Pnueli इसके लिए एक टूरिंग अवार्ड प्राप्त!