मैट्रिक्स आपरेशन के माध्यम से एन-partite ग्राफ

Question

मैं एक n partite (अनिर्दिष्ट) ग्राफ, एक निकटता मैट्रिक्स के रूप में दिया उदाहरण के लिए, यहाँ यह एक है सभी रास्ते की गणना करने में:

 
    a b c d 
a 0 1 1 0 
b 0 0 0 1 
c 0 0 0 1 
d 0 0 0 0 

मैं करना चाहते हैं पता करने के लिए मैट्रिक्स ऑपरेशंस का एक सेट है जिसे मैं इस मैट्रिक्स पर लागू कर सकता हूं, जिसके परिणामस्वरूप एक मैट्रिक्स होगा जो इस ग्राफ में सभी पथों (लंबाई एन, यानी सभी विभाजनों के माध्यम से) "सूचियां" देगा। उपर्युक्त उदाहरण के लिए, पथ ए-> बी-> डी और ए-> सी-> डी हैं। इसलिए, मैं एक परिणाम के रूप में निम्नलिखित मैट्रिक्स प्राप्त करना चाहते हैं:

 
a b c d 
1 1 0 1 
1 0 1 1 

पहले पथ नोड्स ए, बी, डी होता है और दूसरा एक नोड एक, सी, डी। यदि आवश्यक हो, तो परिणाम मैट्रिक्स में कुछ ऑल -0 लाइनें हो सकती हैं, जैसे कि:

 
a b c d 
1 1 0 1 
0 0 0 0 
1 0 1 1 
0 0 0 0 

धन्यवाद!

पीएस मैंने ट्रांजिटिव क्लोजर की गणना करने के लिए एल्गोरिदम को देखा है, लेकिन ये आमतौर पर केवल बताते हैं कि दो नोड्स के बीच कोई पथ है, और सीधे उस पथ पर कौन से नोड्स हैं।

Answer 1

एक चीज जो आप कर सकते हैं वह है मैट्रिक्स ए की एनएच पावर की गणना करना। परिणाम आपको बताएगा कि किसी एक कशेरुक से किसी भी अन्य लंबाई में कितने पथ हैं।

अब यदि आप पथ के साथ सभी शीर्षकों को जानने में रुचि रखते हैं, तो मुझे नहीं लगता कि शुद्ध मैट्रिक्स संचालन का उपयोग करने का तरीका है। इस बात को ध्यान में रखते हुए कि आपके पास एक एन-पार्टिट ग्राफ़ है, मैं निम्नानुसार एक डेटा संरचना स्थापित करूँगा: (ध्यान रखें कि अंतरिक्ष लागत सभी के लिए महंगी महंगी होगी।)

प्रत्येक कॉलम में एक प्रविष्टि होगी हमारे ग्राफ में प्रत्येक नोड्स। एन-वें कॉलम में 1 होगा यदि यह नोड हमारे नामित प्रारंभ वर्टेक्स से एन-वें पुनरावृत्ति पर पहुंच योग्य है या सेट शुरू करें, और शून्य अन्यथा। प्रत्येक कॉलम एंट्री में एन-1 कॉलम में शिखर पर बैक पॉइंटर्स की एक सूची भी शामिल होगी जो इस वर्टेक्स को एनएच कॉलम में ले जाती है। (यह viterbi एल्गोरिदम की तरह है, सिवाय इसके कि हमें केवल एक के बजाय प्रत्येक प्रविष्टि के लिए बैकपॉइंटर्स की एक सूची बनाए रखना है।) ऐसा करने की जटिलता है (एम^2) * एन, जहां एम में चरम की संख्या है ग्राफ, और एन वांछित पथ की लंबाई है।

मैं आपके शीर्ष मैट्रिक्स द्वारा थोड़ा उलझन में हूं: एक अपरिचित ग्राफ के साथ, मैं आसन्नता मैट्रिक्स को सममित होने की अपेक्षा करता हूं।

Answer 2

नहीं, सभी पथ उत्पन्न करने के लिए कोई शुद्ध मैट्रिक्स तरीका नहीं है। कृपया शुद्ध संयोजक एल्गोरिदम का उपयोग करें।

'एक चीज जो आप कर सकते हैं वह है मैट्रिक्स ए की एनएच पावर की गणना करना। परिणाम आपको बताएगा कि किसी एक कशेरुक से किसी भी अन्य लंबाई में कितने पथ हैं।'

मैट्रिक्स उत्पन्न करने की शक्ति पथ नहीं चलती है।