বেসিক গ্রাফ থিওরির টুকিটাকি(Basics of Graph Theory)

 কম্পিউটার বিজ্ঞানের অত্যন্ত গুরুত্বপূর্ণ বিষয় হচ্ছে "গ্রাফ থিওরি"। লিওনার্দ অয়লার ১৭৩৫ সালে কনিসবার্গের সাতটি সেতু সমস্যা সমাধান করেন গ্রাফ থিওরি দিয়ে। সেই থেকে পৃথিবীর মানুষের পরিচয় ঘটে গ্রাফ থিওরির সাথে। এখন প্রশ্ন হচ্ছে, গ্রাফ কি?

যদি বাংলাদেশের মানচিত্র কল্পনা করি তাহলে, এখানে ৬৪ টি শহর আছে। আবার, প্রতি দুইটি শহরের মাঝে প্রত্যেক্ষ অথবা পরোক্ষ ভাবে পথ আছে। তাহলে, শহর এবং পথ মিলে দেশের মানচিত্র হয়। আসলে এটিই কিন্তু একটি গ্রাফ। যেখানে, শহর গুলো হচ্ছে "নোড"(Node) এবং পথগুলো হচ্ছে "এজ"(Edge)। তাহলে, বলতে পারি কিছু নোড এবং এজ মিলে যে চিত্র তৈরি করে তাকে "গ্রাফ" বলা যায়।

এখানে, ঢাকা হচ্ছে শহর 1, টাংগাইল হচ্ছে শহর 2, গাজীপুর হচ্ছে শহর 3 এবং ময়মনসিংহ হচ্ছে শহর 4। আর এখানে এমন বলা নেই যে, ঢাকা থেকে টাংগাইল যাওয়া যাবে কিন্তু টাংগাইল থেকে ঢাকা যাওয়া যাবে না। সুতরাং এটি একটি "আনডিরেক্টেড" বা, "বাইডিরেকশনাল গ্রাফ"। আবার, এই গ্রাফে এক শহর থেকে অন্য শহরে যেতে কত সময় লাগবে বা, কত দূরত্ব তা কিছু বলা নেই। গ্রাফের ক্ষেত্রে সবার দূরত্ব বা, সময় ১ হলে তাহলে উল্লেখ না করলেও চলে। আর সমান হলে সেটি "আনওয়েটেড গ্রাফ"। 

এখানে ঢাকা থেকে ময়মনসিংহ যাওয়ার পথ কয়টি? উত্তর হচ্ছে 4 টি! 
1 > 2 > 4
1 > 2 > 3 > 4
1 > 3 > 4
1 > 3 > 2 > 4

এখন ধরি, ঢাকা থেকে টাংগাইল বা, শহর 1 থেকে শহর 2 তে যেতে বা, আসতে 3 ঘন্টা সময় লাগে। তাহলে কোন পথে গেলে ঢাকা থেকে ময়মনসিংহ যেতে সবচেয়ে কম সময় লাগবে? আশাকরি বের করে ফেলতে পারবেন। আবার, যেহেতু এই গ্রাফে এক শহর থেকে অন্য শহরে যেতে কত সময় লাগবে তার উল্লেখ আছে সেহেতু, এটিকে বলা যায় "ওয়েটেড গ্রাফ"।

এখানে, শহর 2 থেকে শহর 3 এ যাওয়া যায় কিন্তু শহর 3 থেকে শহর 2 তে যাওয়া যায় না। এটিকে বলা যায় "ডিরেক্টেড গ্রাফ"।

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

তাহলে, এখন পর্যন্ত বেসিক গ্রাফ থিওরি থেকে যা যা শিখে ফেলেছি তা হচ্ছে,
নোড(Node)
এজ(Edge)
গ্রাফ(Graph)
ডিরেক্টেড গ্রাফ(Directed Graph)
আনডিরেক্টেড গ্রাফ(Undirected Graph)
ওয়েটেড গ্রাফ(Wieghted Graph)
আনওয়েটেড গ্রাফ(Unwieghted Graph)
পথ(Path)

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

এই বিষয়ে আরো টিউটোরিয়াল।
টিউটোরিয়াল ১