গ্রাফ থিওরি - পর্ব-২ ( অ্যাডজেসেন্সি ম্যাট্রিক্স )

ম্যাট্রিক্স এর সাথে আমরা মোটামুটি পরিচিত। নাহলেও সমস্যা না। ম্যাট্রিক্স হল ১টা 2D অ্যারে। যেমন A একটি ম্যাট্রিক্স। এখানে ,A = 

আমরা ইচ্ছা করলে আমাদের গ্রাফ এর পুরো কথা এই ১টা মাত্র ম্যাট্রিক্স এর সাহায্যে তুলে ধরতে পারি। আপাতত সেটা না করে আমরা যদি এটা শুধু মাথায় রাখি যে যদি A হতে B  তে যাওয়া যায় তাহলে আমরা বলবো 1 . আর তা না হলে বলবো 0.  আমরা গতদিন যে অ্যাডজাসেন্ট নোড দেখেছিলাম এটা আসলে সেটাই। মানে যদি  নোড A আর  নোড B অ্যাডজাসেন্ট নোড হয় তাহলে আমরা বলবো 1. আর তা না হলে 0.

যেমন আমি যদি ১টি  গ্রাফ দেখি -

এখানে, ম্যাট্রিক্সটা হবে এরকম।

ব্যাপারটা হল, নোড A হতে শুধু নোড B এবং C তে যাওয়া সম্ভব। তাই এই দুইটার মান হবে ১ । আর বাকিগুলা ০।

তেমনি নোড B হয়ে শুধু নোড F এ যাওয়া সম্ভব। তাই এর মান হবে ১।

এভাবে নোড C হতে নোড E তে যাওয়া সম্ভব। নোড D হতে নোড A এবং C তে যাওয়া সম্ভব। তাই এর মান হবে ১।

.................................................................................( এভাবেই ম্যাট্রিক্সটা আপাতত গঠন করা হল )

এখানে যদি তীর চিহ্ন না দেয়া থাকে তার মানে হল উভয় নোড থেকে যাওয়া আসা করা যায়।

যেমনঃ

এই গ্রাফ এর ক্ষেত্রে ম্যাট্রিক্স টা হবেঃ

কেন এরকম হল??
আসলে আমরা জানি যে A আর  B এই দুই নোড এর মধ্যের এজ এ তীর চিহ্ন না দেয়ার মানে হল A হতে B তে আসা যাবে। আবার  B হতে  A তেও আসা যাবে । সেজন্য উভয়ক্ষেত্রে এর মান 1 দিতে হইসে। এটাই হল ম্যাট্রিক্স এর শুরু। এবং এখান থেকেই সব সমস্যার সমাধান করতে হয়।

ধন্যবাদ ।