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

ম্যাট্রিক্স এর সাথে আমরা মোটামুটি পরিচিত। নাহলেও সমস্যা না। ম্যাট্রিক্স হল ১টা 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 দিতে হইসে। এটাই হল ম্যাট্রিক্স এর শুরু। এবং এখান থেকেই সব সমস্যার সমাধান করতে হয়।

ধন্যবাদ ।

গ্রাফ থিওরি - পর্ব-১ ( সাধারণ আলোচনা)

আমাদের অনেকের ধারণা গ্রাফ থিওরি মানেই হল একগাদা হাবিজাবি চিত্র আর হাজার হাজার লাইন এর কোড। ব্যাপারটা আসলে সেটা না। এটা আসলে অনেক বিচিত্র ১টা ক্ষেত্র। যেমন আমরা আমাদের প্রতিদিনের অনেক কিছুই এই গ্রাফ থিওরি দিয়েই সমাধান করি। যেমন ধর তুমি যখন স্কুল থেকে বাসায় যাও, রিক্সাওয়ালা চাচা তোমাকে সব চেয়ে শর্টকাট পথ দিয়ে নিয়ে যেতে চায়। আর সেই রাস্তা যদি ভাঙ্গা থাকে বা অন্য কোন সমস্যা থাকে তাহলে তিনি অন্য যে পথটা সবচেয়ে শর্টকাট হয় সেটা বিবেচনায় আনেন। মজার ব্যাপার হল তিনি অজান্তেই গ্রাফ থিওরি ব্যাবহার করছেন। এটা গ্রাফ থিওরির অনেক ব্যাসিক ১টা কথা। অনেকে মনে করে যে আমরা স্কুল কলেজে যে গ্রাফ পেপার এ জ্যামিতি করেছি এটাই গ্রাফ থিওরি.......... কিন্তু প্রকৃত পক্ষে এর সাথে গ্রাফ থিওরির কোন সম্পর্ক নায়।

Graph - 1.1

ধরি এটা ১টা শহরের ম্যাপ। এখানে ৬টা শহর আছে। A,B,C,D,E,F

শহর B হতে শহর A তে আসা যায়। তেমনি C হতে  B, E হতে C এবং F হতে  C তে আসা যায়। বোঝা যাচ্ছে ম্যাপ এ তীর চিহ্ন দেখে। এখন কথা হল এর সাথে গ্রাফ এর কি সম্পর্ক !

ব্যাপারটা হল প্রতিটা শহর এর কেন্দ্র থেকে আসলে এটা ( দূরত্ব )  হিসাব করা হয়। গ্রাফ এর ভাষায় একে বলে নোড (Node) । আর এখানে যে রাস্তা দেখা যাচ্ছে সেটাকে বলা হয় এজ( Edge)।

তো এখানে মোট নোড আছে ৬টা। আর এজ আছে ৪টা। আসল ব্যাপারটা হল পজিশন আর রাস্তা।যেমন দাবা খেলায় ঘোড়া ( Knight ) থাকে। ( আমরা যেটাকে বলি যে  ঘোড়া আড়াই কোট যেতে পারে ) তাহলে ১টা দাবার ছকটা এমন হতে পারে -

Graph - 1.2

এখানে তাহলে তার নোড হবে  a-3,a-5,b-2,b-6,c-4,,d-2,d-6,e-3 এবং e-5 । আর এজ হবে c-4 থেকে বাকি এজগুলার সংযোগ।
আশা করি নোড আর এজ এই ২টা টার্ম ক্লিয়ার ।

Adjacent Node :

অ্যাডজাসেন্ট নোড হল যদি ২টা নোড এর মধ্যে সরাসরি সংযোগ থাকে। যেমন ১ম চিত্রে নোড B হতে নোড A তে সরাসরি সংযোগ আছে। তাই A কে বলা হবে নোড B এর অ্যাডজাসেন্ট নোড।

অনেকসময় গ্রাফ এ কোন তীর চিহ্ন দেয়া থাকবে না। এর মানে হল এটা উভমুখী। যেমন 

Graph - 1.3

এটার বদলে শুধু এরকমও থাকতে পারে

Graph - 1.4

একই কথা।

...................................................................................................................................................................

আবার ১ম চিত্রঃ
এখানে প্রতিটা এজ এর পাশে লেখা আছে যে সেই দূরত্বটা কত কিলোমিটার। আসলে এটাকে বলা হয় কস্ট/ওয়েট ( Cost/Weight) ।আমরা এটাকেই নিয়ে সাধারনত সব হিসাব করি। যেমন নোড B হতে নোড A এর Distance 10KM । এই ওয়েটের মান যদি দেয়া না থাকে তাহলে তার সাধারণ মান হয় ১।


এই পথ যদি না শেষ হয় .................

গ্রাফ থিওরিতে পথ কে পাথ( Path ) বলা হয় । যেমনঃ

Graph - 1.5

C হতে A তে যাওয়ার ২টা উপায় আছে।

1. Cহতে B তে যাওয়া এবং তারপর B হতে A তে যাওয়া।
2. সরাসরি C হতে A তে যাওয়া।

এখানে উভয়ই হল C হতে A তে যাওয়ার পাথ(Path) ।

শর্টেস্ট পাথঃ
কত কম ওয়েটে এক নোড হতে অপর নোড এ যাওয়া যায় =  শর্টেস্ট পাথ।
যেমন, এখানে ১ম উপায়ে ( Cহতে B তে যাওয়া এবং তারপর B হতে A তে যাওয়া ) মোট ওয়েট লাগে ১৮। আর ২য় উপায়ে (সরাসরি C হতে A তে যাওয়া ) সেটা লাগে ২১। সুতরাং তুমি নিশ্চয় ১ম পাথ ব্যাবহার করতে চাইবা। এটাই হল শর্টেস্ট পাথ।( এ ব্যাপার এ পরে আরো বিস্তারিত আলচনা করা হবে ) ।





আশা করি মোটামুটি বোঝাতে পারলাম। এখন কথা হল গ্রাফ থিওরি কেন দরকার? আমরা যে শুধু ট্রাফিক পলিশ দের মত রাস্তার হিসাব দেখবো তা না। আসলে অনেক সময় ডেটা কোন সোর্স থেকে কোন ডিভাইস এ যাবে এবং কোন পাথ ব্যাবহার করবে সেটা এই থিওরি ছাড়া সম্ভব হয় না। নেটওয়ার্কিং এর জন্য গ্রাফ থিওরি একদমই ফরজ। আর এগুলা ছাড়াও আরো অনেক কিছু আছে যা এই গ্রাফ থিওরির সাহায্যে সমাধান করতে হয়। আমরা প্রধানত কন্টেস্ট এর জন্য অনেক সমস্যার আলোচনা করবো পরবর্তী সব পোস্ট এ ।

ধন্যবাদ।