क्या टॉपोलॉजिकल सॉर्टिंग को स्लाइस या किनारों को सॉर्ट करने का प्रयास कर रहा है?

Question

हैप्पी ईस्टर्स, हर कोई।

मैं वर्तमान में स्थलीय प्रकार सीख रहा हूं और इस बारे में एक सवाल है कि कौन सा टोपोलॉजिकल सॉर्ट वास्तव में सॉर्ट करने की कोशिश करता है।

Algorithm Design Manual इस तरह से संस्थानिक तरह वर्णन करता है:

Topological छंटाई निर्देशित अचक्रीय रेखांकन (DAGs) पर सबसे महत्वपूर्ण ऑपरेशन है। यह एक रेखा पर शिखर का आदेश देता है जैसे कि सभी निर्देशित किनारों को बाएं से दाएं जाना जाता है।

यह साहसिक हिस्सा मुझे भ्रमित करता है। तो क्या टोपोलॉजिकल सॉर्टिंग सॉर्ट वर्टिस या सभी निर्देशित किनारों को करता है?

चलो एक उदाहरण लें जो पुस्तक में भी है।

तो DAG ऊपर के लिए

, हम एक सांस्थितिकीय प्रकार (जी, ए, बी, सी, एफ, ई, डी) प्राप्त कर सकते हैं।

मैं इस तरह समझ सकता हूं। all directed edges go from left to right

: इतना ही नहीं कोने हल कर रहे हैं, लेकिन किनारों भी हल कर रहे हैं, यानी, जी> A-> बी> सी> F-> ई> डी, इस से ऊपर ADM पुस्तक विवरण से मेल खाती लेकिन अगर मैं बी-> सी के किनारे को हटा देता हूं तो क्या होगा? परिणामी ग्राफ अभी भी एक डीएजी है, लेकिन क्या स्थलीय प्रकार अभी भी (जी, ए, बी, सी, एफ, ई, डी) होगा?

यदि यह हाँ है, तो मुझे लगता है कि किनारों को क्रमबद्ध नहीं किया गया है, क्योंकि ए-> बी-> सी मौजूद नहीं है, इसके बजाय, यह ए-> बी और ए-> सी है। तो, यह मामला अभी भी एक वैध स्थलीय प्रकार है? क्या हम अभी भी सोच सकते हैं (जी, ए, बी, सी, एफ, ई, डी) एक मान्य प्रकार है भले ही ए बी और सी के माता-पिता हों?

धन्यवाद

Answer 1

आप इसे तत्वों के क्रम के रूप में सोच सकते हैं।

v1, v2, ..., vn तत्व बनें। और किनारे (vi,vj) को vi<vj बताएं। संस्थानिक तरह की गारंटी देता है कि छंटाई के बाद: हर vi के लिए, और हर vj ऐसी है कि i < j के लिए, vj अधिक नहीं तो vi

या अन्य अंकन में है: मान (vi,vj) संकेत मिलता है कि vjvi पर निर्भर है, संस्थानिक प्रकार की गारंटी देता है प्रत्येक कि तत्व "किसी भी तत्व पर निर्भर नहीं है" जो इसके बाद प्रकट होता है।

तो क्या टोपोलॉजिकल सॉर्टिंग सॉर्ट वर्टिस या सभी निर्देशित किनारों को करता है?

टोपोलॉजिकल सॉर्ट प्रकारों को किनारों पर नहीं, किनारों पर। यह किनारों को क्रमबद्ध करने के लिए बाधाओं के रूप में किनारों का उपयोग करता है।

लेकिन अगर मैं बी-> सी के किनारे को हटा देता हूं तो क्या होगा?

हाँ, आप जो भी किनारा जोड़ते हैं, बस एक बाधा जोड़ें।ध्यान दें कि स्थलीय प्रकार के लिए एक व्यवहार्य समाधान हो सकता है [उदाहरण के लिए, बिना किनारों के ग्राफ के लिए, कोई क्रमपरिवर्तन एक व्यवहार्य समाधान है]। एक बाधा को दूर करना, कोई पिछला समाधान बनाता है, जो "एक कठिन समस्या हल करता है" अभी भी व्यवहार्य है।

हम अभी भी सोच सकते हैं (जी, ए, बी, सी, एफ, ई, डी) एक वैध तरह भले ही एक बी और सी की मूल है?

इसमें कोई समस्या नहीं है! बी, सी को टोपोलॉजिकल सॉर्ट में दिखाई देता है, इसलिए उनके पिता की कोई समस्या नहीं है।

आशा है कि यह थोड़ा और स्पष्ट हो जाए।