मुझे लगता है कि मैंने नीचे वर्णित एक विशेष स्थिति को समझ लिया है, लेकिन मुझे प्रमाण प्रस्तुत करने के लिए सैद्धांतिक ज्ञान की कमी है और मुझे इसका कोई स्रोत नहीं मिला। अगर मेरी समझ सही है, तो मैं अपने आसन्न मैट्रिक्स पर आधे स्थान को बचा सकता हूं, अगर ऐसा नहीं है तो मुझे बहुत अजीब बग होने की संभावना है। तो मैं निश्चित रूप से सुनिश्चित करना चाहता हूं, और अगर मैं अधिक ठोस पृष्ठभूमि वाला कोई व्यक्ति मेरी तर्क की समीक्षा कर सकता हूं तो मैं सराहना करता हूं।यदि मैं एक डीएजी को स्थाई रूप से सॉर्ट करता हूं, तो क्या मैं आधा आसन्न मैट्रिक्स छोड़ सकता हूं?
मैं एक n * n निकटता मैट्रिक्स में n कोने की एक DAG प्रतिनिधित्व कहो ऐसी है कि प्रवेश i,j1 है अगर वहाँ शिखर i से बढ़त अन्यथा j, 0 शीर्ष के है। चूंकि ग्राफ निर्देशित और विश्वकोश है, इसलिए यह i,j = 1 है, तो j,i = 0। यदि अब मैं मैट्रिक्स में नोड्स को सॉर्ट करता हूं जैसे कि n पर नोड का स्थलीय स्तर i n-1 पर नोड के बराबर या उससे अधिक है, तो मुझे लगता है कि आसन्नता मैट्रिक्स का आधा हमेशा ही 0 रों होते हैं, के रूप में यह निम्न उदाहरण में मामला है:
V 1 V 2 from V 1 2 3 4 5 6 7 8
/\ /\
/ \ / \ to V 1 0 0 0 0 0 0 0 0
/ \ / \ 2 0 0 0 0 0 0 0 0
e1/ e2\ e3/ e4\ 3 1 0 0 0 0 0 0 0
/ \ / \ 4 1 1 0 0 0 0 0 0
V 3 V 4 V 5 5 0 1 0 0 0 0 0 0
/|\ / 6 0 0 0 1 0 0 0 0
/| \ / 7 0 0 0 1 0 0 0 0
/| \ / 8 0 0 0 1 1 0 0 0
e5/ e6| e7\ e8/
/ | \/
V 6 V 7 V 8
शायद मैं सिर्फ सही कर रहा हूँ, लेकिन इस जांच करने के लिए एक औपचारिक तरीका है?
धन्यवाद। यह उचित शर्तों में मेरा आंत महसूस कर रहा है। मेरे पास बहुत कम प्रशिक्षण है। –