This post is also available in: English
किसी भी n नोड्स के ग्राफ को n आर्डर की स्क्वायर मैट्रिक्स से दर्शाया जा सकता है। इस लेख में, हम बच्चों के लाभ के लिए समझाए गए ग्राफ़ के 2 आवश्यक अवधारणाओं को ले कर आये हैं। ये हैं अडजैसेन्सी मैट्रिक्स और पाथ मैट्रिक्स।
आसन्न मैट्रिक्स और पथ मैट्रिक्स
एक नेटवर्क में आमतौर पर एक दूसरे से जुड़े सैकड़ों या हजारों नोड्स होते हैं। इन नेटवर्कों को ग्राफ, एक प्रकार की डेटा स्ट्रक्चर के रूप में दर्शाया जा सकता है। क्या आपने कभी सोचा है कि निर्बाध संचार की सुविधा के लिए दो नोड्स के बीच एक मार्ग कैसे स्थापित किया जाता है?
इसे समझने के लिए, किसी को ग्राफ की दो मूल अवधारणाओं को जानना आवश्यक है।
- अडजैसेन्सी मैट्रिक्स
- पाथ मैट्रिक्स
अडजैसेन्सी मैट्रिक्स
ग्राफ सिद्धांत और कंप्यूटर विज्ञान में, एक अडजैसेन्सी मैट्रिक्स एक वर्ग मैट्रिक्स है जिसका उपयोग परिमित ग्राफ का प्रतिनिधित्व करने के लिए किया जाता है। मैट्रिक्स के तत्व इंगित करते हैं कि क्या ग्राफ में शीर्ष के जोड़े में आसन्न हैं या नहीं।
एक अडजैसेन्सी मैट्रिक्स के एलिमेंट 0 या 1 होते हैं। यदि नोड्स की एक जोड़ी में एक कॉमन एज्ज है (यानी, नोड्स जुड़े हुए हैं), तो यह 1 द्वारा दर्शाया गया है। यदि नोड्स की एक जोड़ी में एक कॉमन एज्ज नहीं है (यानी, नोड्स जुड़े नहीं हैं), यह 0 से दर्शाया गया है।
आइए अब समझते हैं कि कैसे एक अडजैसेन्सी मैट्रिक्स द्वारा अनिर्देशित और निर्देशित ग्राफ़ कैसे दर्शाये जाते हैं।
Adjacency Matrix – Undirected Graph
इस ग्राफ में नोड ए, नोड बी और सी के समीप है, इसी प्रकार नोड बी नोड ए और सी के निकट है; नोड सी नोड्स ए, बी और डी के निकट है; नोड डी नोड सी के समीप है।
उपरोक्त ग्राफ की अडजैसेन्सी मैट्रिक्स है
| A | B | C | D | ||||||
| A | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |
| B | 1 | 0 | 1 | 0 | = | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
| D | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
उपरोक्त मैट्रिक्स में, चूंकि ए से सी के साथ-साथ सी से ए तक का पथ है, इसलिए ए से सी और सी से ए को 1 से दर्शाया गया है। अन्य नोड्स के लिए भी यही नियम लागू होता है।
जब एक नोड एक लूप द्वारा खुद से जुड़ा होता है। (नोड सी में एक लूप है)।
| A | B | C | D | ||||||
| A | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |
| B | 1 | 0 | 1 | 0 | = | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| D | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
Adjacency Matrix – Directed Graph
ऊपर दिखाये गये निर्देशित ग्राफ पर विचार करें। नोड ए से नोड बी तक एक पथ है, लेकिन नोड बी से नोड ए तक कोई सीधा पथ मौजूद नहीं है। इसी तरह नोड सी से नोड ए तक पथ है, लेकिन नोड ए से नोड सी के बीच ऐसा कोई पथ नहीं है।
अब नोड बी और सी की एक जोड़ी पर विचार करें। नोड बी से नोड सी के साथ-साथ नोड सी से नोड बी तक एक सीधा पथ है। उपरोक्त ग्राफ की अडजैसेन्सी मैट्रिक्स को निम्न रूप में दर्शाया गया है।
| A | B | C | D | ||||||
| A | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | |
| B | 0 | 0 | 1 | 0 | = | 0 | 0 | 1 | 0 |
| C | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
पाथ मैट्रिक्स
निम्नलिखित ग्राफ पर विचार करें
उपरोक्त ग्राफ की अडजैसेन्सी मैट्रिक्स है
| A | B | C | D | E | |||||||
| A | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | |
| B | 0 | 0 | 1 | 0 | 0 | = | 0 | 0 | 1 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | |
| D | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| E | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
यदि हम उपरोक्त अडजैसेन्सी मैट्रिक्स से नोड बी और ई की जोड़ी पर विचार करते हैं, तो हम पाते हैं कि बी और ई के बीच कोई सीधा पथ नहीं है। लेकिन सी के माध्यम से बी और ई से एक पथ मौजूद है। इस तरह के पथ को लंबाई २ के पथ के रूप में जाना जाता है। इसी प्रकार, लंबाई 3 के पथ में 2 मध्यवर्ती नोड होंगे। सामान्य तौर पर, लंबाई n के किसी भी पथ में (n – 1) मध्यवर्ती नोड होंगे।
लंबाई 2 के पाथ मैट्रिक्स को प्राप्त करने के लिए, अडजैसेन्सी मैट्रिक्स को खुद से गुणाकिया जाता है।
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | ||
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | ||
| 0 | 0 | 0 | 0 | 1 | ✕ | 0 | 0 | 0 | 0 | 1 | = | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ||
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
उपरोक्त मैट्रिक्स से, हम पाते हैं कि A से B, E से B, A से C, D से C, C से D और B से E के बीच लंबाई 2 का पथ मौजूद है।
दोबारा अडजैसेन्सी मैट्रिक्स के साथ लंबाई 2 के पाथ मैट्रिक्स को गुणा करने पर पथ 3 की पाथ मैट्रिक्स मिलती है।
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | ||
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | ||
| 0 | 0 | 0 | 1 | 0 | ✕ | 0 | 0 | 0 | 0 | 1 | = | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | ||
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
उपरोक्त मैट्रिक्स से, हम पाते हैं कि C से B, A से C, E से C, B से D, A से E और D से E के बीच लंबाई 3 का पथ मौजूद है।
सामान्य तौर पर, लंबाई n के पाथ मैट्रिक्स को प्राप्त करने के लिए, लंबाई (n – 1) के पाथ मैट्रिक्स को लें, और इसे लंबाई 1 के पाथ मैट्रिक्स से गुणा करें।
