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

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

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





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

ধন্যবাদ।