আমরা এখন কোথাও যেতে প্রায়ই উবার কিংবা পাঠাও ব্যবহার করি। কিন্তু একবারও কি চিন্তা করে দেখা হয়েছে উবার কিংবা পাঠাও এর পেছনে কোন টেকনোলজি কাজ করছে?? উবার তাদের অনেক উন্নত ও এফিসিয়েন্ট প্রযুক্তির সাথে গ্রাফ থিওরির কনসেপ্ট ব্যবহার করছে। শুধু উবার কেন?? আমাদের পছন্দের সামাজিক যোগাযোগের মাধ্যম ফেসবুকের কোনো ইনফরমেশন তাদের সার্ভার থেকে কিভাবে অনেক গুলো রাউটার ও সুইচ পার করে আমাদের মোবাইল কিংবা ল্যাপটপে আসছে তা চিন্তা করা হয় নি নিশ্চয় কখনো। এখানেও গ্রাফ থিওরির কনসেপ্ট ব্যবহার করা হয়। এমন অনেক প্রযুক্তিতে গ্রাফ থিওরি কাজে লাগানো হয়েছে।
গ্রাফের ডেফিনিশন জানার আগে চট্টগ্রাম শহর নিয়ে একটি গ্রাফ কল্পনা করি। এখানে বৃত্ত দ্বারা চট্টগ্রাম শহরের বিভিন্ন স্থানকে বোঝানো হয়েছে এবং সরলরেখা গুলো স্থানগুলোর মধ্যে রাস্তা নির্দেশ করছে।
উপরের চিত্রে বৃত্ত নির্দেশিত স্থানগুলোকে গ্রাফ থিওরির ভাষায় বলে Node বা Vertex এবং লাল সরলরেখা গুলোকে বলে Edge | এইসব Node এবং Edge এর কালেকশনকেই বলে গ্রাফ। আমরা যখন গ্রাফের বিভিন্ন প্রব্লেম সল্ভ করবো তখন দেখবো কিভাবে শহর, স্টেশন, দেশ বা কোনো স্থানকে Node হিসেবে কল্পনা করে তার সল্যুশন বের করতে হয়। Edge এই স্থানগুলোর মধ্যে বিভিন্ন সম্পর্ক বুঝতে বা সংযোগ বুঝতে ব্যবহৃত হয়।
এবার আমরা গ্রাফ থিওরির কয়েকটি টার্ম নিয়ে পরিচিত হবো।
ডিরেক্টেড গ্রাফ, আনডিরেক্টেড গ্রাফ: যেসকল গ্রাফে তীর চিহ্ন থাকে তাদের ডিরেক্টেড গ্রাফ বলে। ডিরেক্টেড গ্রাফ সাধারণত Unidirectional হয়। অপরদিকে যেসকল গ্রাফে তীর চিহ্ন থাকে না তাদের আনডিরেক্টেড গ্রাফ বলে। আনডিরেক্টেড গ্রাফ সাধারণত Bidirectional হয়
অ্যাডজেসেন্ট নোড: অ্যাডজেসেন্ট নোড হলো একটি নোড থেকে Edge দ্বারা কানেক্টেড যেসকল নোডে যাওয়া যায় সেসকল নোড।
ওয়েটেড, আনওয়েটেড গ্রাফ: উপরের চট্টগ্রাম শহরের গ্রাফে একটি স্থান থেকে অপর স্থানে যেতে যে দূরত্ব অতিক্রম করতে হয়, সেটি ওই দুই স্থানের সংযোগকারী Edge এর Weight বা Cost। গ্রাফের প্রব্লেম সল্ভ করতে গিয়ে আমরা Edge এর পাশে কিছু সংখ্যা দেখতে পাবো এগুলোই হচ্ছে Weight। যেসব গ্রাফে Edge এর পাশে কোনো সংখ্যা থাকবে না সেইগুলো আনওয়েটেড গ্রাফ। আনওয়েটেড গ্রাফে Weight বা Cost 1 ধরে নেয়া হয়।
ডিগ্রী: ডিরেক্টেড গ্রাফে একটি নোডে কয়টি এজ প্রবেশ করেছে তাকে ইনডিগ্রী, কোন নোড থেকে কয়টি এজ বের হয়েছে তাকে আউটডিগ্রী বলে। আনডিরেক্টেড গ্রাফে ইন বা আউটডিগ্রী আলাদা করা হয়না। একটা নোডের যতগুলো অ্যাডজেসেন্ট নোড আছে সেই সংখ্যাটাই নোডটির ডিগ্রী।
No comments:
Post a Comment