গ্রাফ থিওরিতে, একটি ভেরটেক্সের নেবারহুড হল সেই ভেরটেক্সগুলোর সেট যা সরাসরি তার সাথে সংযুক্ত থাকে। সহজভাবে বলতে, একটি ভেরটেক্সের নেবারহুড হল তার পার্শ্ববর্তী ভেরটেক্সগুলোর সমষ্টি।
নেবারহুডের কিছু বৈশিষ্ট্য:
সংজ্ঞা:
যদি v একটি ভেরটেক্স হয়, তবে N(v) এর মাধ্যমে v এর নেবারহুড নির্দেশ করা হয়, যা v এর সাথে সংযুক্ত সব ভেরটেক্সের সেট।
উদাহরণ:
যদি গ্রাফে A, B, C এবং D ভেরটেক্স থাকে এবং A এর সাথে B এবং C যুক্ত থাকে, তবে A এর নেবারহুড হবে N(A)={B,C}।
ডাইরেক্টেড গ্রাফের ক্ষেত্রে:
ডাইরেক্টেড গ্রাফে, নেবারহুডে ইনডিগ্রি এবং আউটডিগ্রি আলাদাভাবে বিবেচিত হয়।
ইন-neighborhood: ভেরটেক্সগুলোর সেট যা নির্দিষ্ট ভেরটেক্সের কাছে আসছে।
আউট-neighborhood: ভেরটেক্সগুলোর সেট যা নির্দিষ্ট ভেরটেক্স থেকে বের হচ্ছে।
ইন্ডিপেনডেন্ট সেট (Independent Set)
একটি গ্রাফের ইন্ডিপেনডেন্ট সেট হল সেই ভেরটেক্সগুলোর একটি সেট, যেখানে কোনও দুই ভেরটেক্সের মধ্যে কোনো এজ নেই। অর্থাৎ, এই সেটের ভেরটেক্সগুলোর মধ্যে একটিও সরাসরি সংযুক্ত নয়।
ইন্ডিপেনডেন্ট সেটের কিছু বৈশিষ্ট্য:
সংজ্ঞা:
একটি গ্রাফ G এর জন্য একটি ভেরটেক্স সেট S ইন্ডিপেনডেন্ট সেট হয় যদি u,v∈S হলে (u,v) কোন এজ না থাকে।
উদাহরণ:
একটি গ্রাফে যদি A, B, C এবং D ভেরটেক্স থাকে এবং A এবং B এর মধ্যে একটি এজ থাকে, তবে {A,C} এবং {B,D} দুটি আলাদা ইন্ডিপেনডেন্ট সেট হতে পারে।
সর্বাধিক ইন্ডিপেনডেন্ট সেট (Maximum Independent Set):
একটি গ্রাফের জন্য সর্বাধিক ইন্ডিপেনডেন্ট সেট হল সেই ইন্ডিপেনডেন্ট সেট যার আকার (ভেরটেক্সের সংখ্যা) অন্য কোন ইন্ডিপেনডেন্ট সেটের থেকে বেশি।
সারসংক্ষেপ
নেবারহুড এবং ইন্ডিপেনডেন্ট সেট গ্রাফ থিওরির গুরুত্বপূর্ণ ধারণা। নেবারহুড একটি ভেরটেক্সের পার্শ্ববর্তী ভেরটেক্সগুলোর সমষ্টি নির্দেশ করে, যেখানে ইন্ডিপেনডেন্ট সেট হল ভেরটেক্সগুলোর একটি সেট, যার মধ্যে কোন সরাসরি সংযোগ নেই। এই ধারণাগুলি গ্রাফের গঠন এবং সম্পর্ক বিশ্লেষণে গুরুত্বপূর্ণ।
