• Home
  • /
  • Blog
  • /
  • बच्चों के लाभ के लिए समझाए गए ग्राफ के 2 आवश्यक अवधारणाएं

बच्चों के लाभ के लिए समझाए गए ग्राफ के 2 आवश्यक अवधारणाएं

Adjacency Matrix and Path Matrix

This post is also available in: English

किसी भी n नोड्स के ग्राफ को n आर्डर की स्क्वायर मैट्रिक्स से दर्शाया जा सकता है। इस लेख में, हम बच्चों के लाभ के लिए समझाए गए ग्राफ़ के 2 आवश्यक अवधारणाओं को ले कर आये हैं। ये हैं अडजैसेन्सी मैट्रिक्स और पाथ मैट्रिक्स

आसन्न मैट्रिक्स और पथ मैट्रिक्स

एक नेटवर्क में आमतौर पर एक दूसरे से जुड़े सैकड़ों या हजारों नोड्स होते हैं। इन नेटवर्कों को ग्राफ, एक प्रकार की डेटा स्ट्रक्चर के रूप में दर्शाया जा सकता है। क्या आपने कभी सोचा है कि निर्बाध संचार की सुविधा के लिए दो नोड्स के बीच एक मार्ग कैसे स्थापित किया जाता है?

इसे समझने के लिए, किसी को ग्राफ की दो मूल अवधारणाओं को जानना आवश्यक है।

  • अडजैसेन्सी मैट्रिक्स
  • पाथ मैट्रिक्स

अडजैसेन्सी मैट्रिक्स

ग्राफ सिद्धांत और कंप्यूटर विज्ञान में, एक अडजैसेन्सी मैट्रिक्स एक वर्ग मैट्रिक्स है जिसका उपयोग परिमित ग्राफ का प्रतिनिधित्व करने के लिए किया जाता है। मैट्रिक्स के तत्व इंगित करते हैं कि क्या ग्राफ में शीर्ष के जोड़े में आसन्न हैं या नहीं।

एक अडजैसेन्सी मैट्रिक्स के एलिमेंट 0 या 1 होते हैं। यदि नोड्स की एक जोड़ी में एक कॉमन एज्ज है (यानी, नोड्स जुड़े हुए हैं), तो यह 1 द्वारा दर्शाया गया है। यदि नोड्स की एक जोड़ी में एक कॉमन एज्ज नहीं है (यानी, नोड्स जुड़े नहीं हैं), यह 0 से दर्शाया गया है।

आइए अब समझते हैं कि कैसे एक अडजैसेन्सी मैट्रिक्स द्वारा अनिर्देशित और निर्देशित ग्राफ़ कैसे दर्शाये जाते हैं।

Adjacency Matrix – Undirected Graph

आसन्न मैट्रिक्स और पथ मैट्रिक्स
Undirected Graph

इस ग्राफ में नोड ए, नोड बी और सी के समीप है, इसी प्रकार नोड बी नोड ए और सी के निकट है; नोड सी नोड्स ए, बी और डी के निकट है; नोड डी नोड सी के समीप है।

उपरोक्त ग्राफ की अडजैसेन्सी मैट्रिक्स है

ABCD
A01100110
B1010=1010
C11011101
D00100010
अडजैसेन्सी मैट्रिक्स

उपरोक्त मैट्रिक्स में, चूंकि ए से सी के साथ-साथ सी से ए तक का पथ है, इसलिए ए से सी और सी से ए को 1 से दर्शाया गया है। अन्य नोड्स के लिए भी यही नियम लागू होता है।

जब एक नोड एक लूप द्वारा खुद से जुड़ा होता है। (नोड सी में एक लूप है)।

आसन्न मैट्रिक्स और पथ मैट्रिक्स
Undirected Graph with Loop
ABCD
A01100110
B1010=1010
C11111111
D00100010
अडजैसेन्सी मैट्रिक्स

Adjacency Matrix – Directed Graph

आसन्न मैट्रिक्स और पथ मैट्रिक्स
Direct Graph with Loop

ऊपर दिखाये गये निर्देशित ग्राफ पर विचार करें। नोड ए से नोड बी तक एक पथ है, लेकिन नोड बी से नोड ए तक कोई सीधा पथ मौजूद नहीं है। इसी तरह नोड सी से नोड ए तक पथ है, लेकिन नोड ए से नोड सी के बीच ऐसा कोई पथ नहीं है।

अब नोड बी और सी की एक जोड़ी पर विचार करें। नोड बी से नोड सी के साथ-साथ नोड सी से नोड बी तक एक सीधा पथ है। उपरोक्त ग्राफ की अडजैसेन्सी मैट्रिक्स को निम्न रूप में दर्शाया गया है।

ABCD
A01000100
B0010=0010
C11111111
D00000000

पाथ मैट्रिक्स

निम्नलिखित ग्राफ पर विचार करें

आसन्न मैट्रिक्स और पथ मैट्रिक्स
डायरेक्टेड ग्राफ़

उपरोक्त ग्राफ की अडजैसेन्सी मैट्रिक्स है

ABCDE
A0101001010
B00100=00100
C0000100001
D0100001000
E0001000010

यदि हम उपरोक्त अडजैसेन्सी मैट्रिक्स से नोड बी और ई की जोड़ी पर विचार करते हैं, तो हम पाते हैं कि बी और ई के बीच कोई सीधा पथ नहीं है। लेकिन सी के माध्यम से बी और ई से एक पथ मौजूद है। इस तरह के पथ को लंबाई २ के पथ के रूप में जाना जाता है। इसी प्रकार, लंबाई 3 के पथ में 2 मध्यवर्ती नोड होंगे। सामान्य तौर पर, लंबाई n के किसी भी पथ में (n – 1) मध्यवर्ती नोड होंगे।

लंबाई 2 के पाथ मैट्रिक्स को प्राप्त करने के लिए, अडजैसेन्सी मैट्रिक्स को खुद से गुणाकिया जाता है।

010100101001100
001000010000001
0000100001=00010
010000100000100
000100001001000

उपरोक्त मैट्रिक्स से, हम पाते हैं कि A से B, E से B, A से C, D से C, C से D और B से E के बीच लंबाई 2 का पथ मौजूद है।

दोबारा अडजैसेन्सी मैट्रिक्स के साथ लंबाई 2 के पाथ मैट्रिक्स को गुणा करने पर पथ 3 की पाथ मैट्रिक्स मिलती है।

011000101000101
000010010000010
0001000001=01000
001000100000001
010000001000100

उपरोक्त मैट्रिक्स से, हम पाते हैं कि C से B, A से C, E से C, B से D, A से E और D से E के बीच लंबाई 3 का पथ मौजूद है।

सामान्य तौर पर, लंबाई n के पाथ मैट्रिक्स को प्राप्त करने के लिए, लंबाई (n – 1) के पाथ मैट्रिक्स को लें, और इसे लंबाई 1 के पाथ मैट्रिक्स से गुणा करें।

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}
>