ডিরেক্টেড এবং আনডিরেক্টেড গ্রাফ
গ্রাফ থিওরিতে, ডিরেক্টেড (Directed) এবং আনডিরেক্টেড (Undirected) গ্রাফ দুটি প্রধান প্রকারের গ্রাফ, যা তাদের সংযোগের দিক এবং সম্পর্কের ভিত্তিতে ভিন্নতা নির্দেশ করে।
১. ডিরেক্টেড গ্রাফ (Directed Graph)
- বর্ণনা: ডিরেক্টেড গ্রাফে (যা ডায়াগ্রাফ নামেও পরিচিত) প্রতিটি এজের একটি নির্দিষ্ট দিক থাকে। অর্থাৎ, একটি নোড থেকে অন্য নোডে যাওয়ার জন্য একটি নির্দিষ্ট নির্দেশনা রয়েছে।
- উদাহরণ:
- যদি A থেকে B তে একটি এজ থাকে, তবে এটি নির্দেশ করে যে A থেকে B তে যাওয়া সম্ভব, কিন্তু B থেকে A তে যাওয়া সম্ভব নয়।
- বিশেষত্ব:
- নোডের ডিগ্রি: ডিরেক্টেড গ্রাফে, প্রতিটি নোডের ইনডিগ্রি (incoming edges) এবং আউটডিগ্রি (outgoing edges) থাকে।
- চিত্র: গ্রাফের চিত্রে, ডিরেক্টেড এজগুলির জন্য তীর (arrow) ব্যবহার করা হয়।
- ব্যবহার:
- সোশ্যাল মিডিয়া ফলোয়ার সম্পর্ক, ওয়েব পেজের লিঙ্ক, ওরাকল ও ডিজাইন ডাটাবেস।
২. আনডিরেক্টেড গ্রাফ (Undirected Graph)
- বর্ণনা: আনডিরেক্টেড গ্রাফে কোন নির্দিষ্ট দিক নেই, অর্থাৎ একটি নোড থেকে অন্য নোডে যাওয়ার ক্ষেত্রে কোন বাধা নেই। দুই নোডের মধ্যে সংযোগ উভয় দিকেই প্রবাহিত হতে পারে।
- উদাহরণ:
- যদি A এবং B এর মধ্যে একটি এজ থাকে, তবে A থেকে B তে যাওয়া এবং B থেকে A তে যাওয়া উভয়ই সম্ভব।
- বিশেষত্ব:
- নোডের ডিগ্রি: আনডিরেক্টেড গ্রাফে প্রতিটি নোডের ডিগ্রি কেবল এজগুলির সংখ্যা বোঝায়।
- চিত্র: গ্রাফের চিত্রে, আনডিরেক্টেড এজগুলির জন্য তীর ছাড়া সরল লাইন ব্যবহার করা হয়।
- ব্যবহার:
- সামাজিক নেটওয়ার্কে বন্ধুত্ব সম্পর্ক, যোগাযোগ নেটওয়ার্ক, রাস্তাঘাটের নেটওয়ার্ক।
সারসংক্ষেপ
ডিরেক্টেড এবং আনডিরেক্টেড গ্রাফগুলি তাদের সম্পর্কের দিক এবং এজগুলির বৈশিষ্ট্যের উপর ভিত্তি করে ভিন্ন। ডিরেক্টেড গ্রাফে নির্দিষ্ট দিক থাকে, যা এক দিকের সম্পর্ক নির্দেশ করে, আর আনডিরেক্টেড গ্রাফে সম্পর্ক উভয় দিকেই প্রবাহিত হতে পারে। এই দুটি গ্রাফের প্রকার বাস্তব জীবনের বিভিন্ন সমস্যা বিশ্লেষণে ব্যবহৃত হয়, যা তাদের গুরুত্বপূর্ণ করে তোলে।
Content added By
Read more
