অ্যাডজেসেন্সি ম্যাট্রিক্স (Adjacency Matrix)
অ্যাডজেসেন্সি ম্যাট্রিক্স হল একটি গ্রাফ রিপ্রেজেন্টেশন পদ্ধতি, যা একটি দুই-মাত্রিক অ্যারে (matrix) ব্যবহার করে গ্রাফের ভেরটেক্স এবং তাদের মধ্যে সংযোগ (এজ) নির্দেশ করে। এই পদ্ধতি ব্যবহার করে গ্রাফের তথ্য সংরক্ষণ এবং বিভিন্ন কার্যক্রম পরিচালনা করা সহজ হয়।
গঠন
- একটি গ্রাফ এর ভেরটেক্স থাকলে, এর অ্যাডজেসেন্সি ম্যাট্রিক্স একটি ম্যাট্রিক্স হবে।
- যদি হয়, তবে এর অর্থ হল ভেরটেক্স এবং এর মধ্যে একটি এজ আছে; অন্যথায় ।
ডাইরেক্টেড ও আনডাইরেক্টেড গ্রাফের জন্য
- ডাইরেক্টেড গ্রাফ: যদি গ্রাফে এজগুলি দিক নির্দেশ করে থাকে, তাহলে মানে থেকে তে একটি এজ আছে।
- আনডাইরেক্টেড গ্রাফ: যদি গ্রাফে এজগুলি দিকহীন হয়, তাহলে এবং উভয়ই হবে।
উদাহরণ
ধরি, আমাদের একটি গ্রাফ আছে যার ভেরটেক্সগুলি A, B, C, D এবং এজগুলি A-B, A-C, B-D।
অ্যাডজেসেন্সি ম্যাট্রিক্স হবে:
এখানে:
- A-B সংযোগের জন্য A এর ১ এবং B এর ১।
- A-C সংযোগের জন্য A এর ১ এবং C এর ১।
- B-D সংযোগের জন্য B এর ১ এবং D এর ১।
সুবিধা
- দ্রুত এজ চেক: অ্যাডজেসেন্সি ম্যাট্রিক্স ব্যবহার করে একটি নির্দিষ্ট ভেরটেক্সের মধ্যে সংযোগ চেক করা দ্রুত (O(1) সময়)।
- সহজ গঠন: ম্যাট্রিক্সের আকার সরাসরি গ্রাফের ভেরটেক্সের সংখ্যা নির্দেশ করে, যা পরিষ্কার।
- ডাইরেক্টেড এবং আনডাইরেক্টেড উভয় গ্রাফের জন্য প্রযোজ্য: অ্যাডজেসেন্সি ম্যাট্রিক্স ডাইরেক্টেড এবং আনডাইরেক্টেড উভয় ধরনের গ্রাফে ব্যবহৃত হতে পারে।
অসুবিধা
- স্থান সংকুলান: অনেক ভেরটেক্স এবং অপ্রয়োজনীয় সংযোগ থাকলে ম্যাট্রিক্সটি বড় আকার ধারণ করে (O(n^2) স্থান)।
- স্পার্স গ্রাফে অপচয়: যদি গ্রাফ স্পার্স (কম এজ) হয়, তবে অনেক স্থান অপচয় হয়, কারণ বেশিরভাগ কোষ শূন্য থাকবে।
সারসংক্ষেপ
অ্যাডজেসেন্সি ম্যাট্রিক্স একটি কার্যকরী গ্রাফ রিপ্রেজেন্টেশন পদ্ধতি, যা ভেরটেক্সগুলির মধ্যে সংযোগ এবং সম্পর্ক নির্দেশ করে। এটি দ্রুত এজ চেকিংয়ের সুবিধা দেয়, তবে স্থান সংকুলানের কারণে বড় এবং স্পার্স গ্রাফগুলির জন্য কার্যকরী নাও হতে পারে।
Content added By
Read more
