সাবগ্রাফ (Subgraph) এবং ইন্ডুসড সাবগ্রাফ (Induced Subgraph)
গ্রাফ থিওরিতে, সাবগ্রাফ এবং ইন্ডুসড সাবগ্রাফ দুটি গুরুত্বপূর্ণ ধারণা যা একটি গ্রাফের অংশকে বোঝায়।
১. সাবগ্রাফ (Subgraph)
- বর্ণনা: সাবগ্রাফ হল মূল গ্রাফের একটি অংশ, যা কিছু ভেরটেক্স এবং তাদের মধ্যে থাকা এজ সম্বলিত। এটি মূল গ্রাফের কোন ভেরটেক্স এবং এজের উপর ভিত্তি করে গঠিত হয়।
- গঠন:
- একটি সাবগ্রাফ তৈরি করতে, আমরা মূল গ্রাফ এর কিছু ভেরটেক্স এবং তাদের মধ্যে থাকা এজ নির্বাচন করি।
- উদাহরণ:
- যদি গ্রাফ এর ভেরটেক্সসমূহ A, B, C, D হয় এবং এজসমূহ A-B, A-C, B-D হয়, তাহলে ভেরটেক্স নিয়ে সাবগ্রাফ গঠন করা যায়, যেখানে এজ হবে A-B।
২. ইন্ডুসড সাবগ্রাফ (Induced Subgraph)
- বর্ণনা: ইন্ডুসড সাবগ্রাফ হল একটি বিশেষ ধরনের সাবগ্রাফ যা একটি নির্দিষ্ট ভেরটেক্স সেটের জন্য তৈরি হয়, যেখানে সেই ভেরটেক্সগুলির মধ্যে থাকা সব এজ অন্তর্ভুক্ত করা হয়। অর্থাৎ, যদি ভেরটেক্সের একটি সেট হয়, তবে ইন্ডুসড সাবগ্রাফ হবে এর সমস্ত ভেরটেক্স নিয়ে গঠিত গ্রাফ, যেখানে এর মধ্যে থাকা ভেরটেক্সগুলির সাথে সমস্ত সংযুক্ত এজ অন্তর্ভুক্ত থাকবে।
- গঠন:
- একটি ইন্ডুসড সাবগ্রাফ তৈরি করতে, প্রথমে একটি ভেরটেক্স সেট নির্বাচন করুন, এবং তারপর এর মধ্যে থাকা সব ভেরটেক্সের মধ্যে সংযুক্ত এজগুলি অন্তর্ভুক্ত করুন।
- উদাহরণ:
- যদি গ্রাফ এর ভেরটেক্সসমূহ A, B, C, D এবং এজসমূহ A-B, A-C, B-D হয়, এবং আমরা নির্বাচন করি, তাহলে ইন্ডুসড সাবগ্রাফ হবে A, B এর জন্য, যেখানে A-B এর এজ থাকবে।
সারসংক্ষেপ
সাবগ্রাফ হল মূল গ্রাফের একটি অংশ, যেখানে কিছু ভেরটেক্স এবং এজ অন্তর্ভুক্ত থাকে। অন্যদিকে, ইন্ডুসড সাবগ্রাফ হল একটি নির্দিষ্ট ভেরটেক্স সেটের জন্য তৈরি করা সাবগ্রাফ, যেখানে সেই সেটের মধ্যে থাকা সমস্ত সংযুক্ত এজ অন্তর্ভুক্ত করা হয়। এই দুটি ধারণা গ্রাফ থিওরি এবং সম্পর্ক বিশ্লেষণের ক্ষেত্রে গুরুত্বপূর্ণ ভূমিকা পালন করে।
Content added By
Read more
