مجموعه ناوابسته

نه گره آبی مجموعهٔ ناوابستهٔ بیشینه‌اند.

مجموعه ناوابسته برای یک گراف مجموعه‌ای از گره‌ها‌ست که هیچ یالی میان هیچ جفتی از این گره‌ها نباشد.

مجموعهٔ ناوابسته بیشین، مجموعه‌ای ناوابسته است که با افزودن گره‌ای دیگر به این مجموعه دیگر ناوابسته نباشد. به سخنی دیگر، با افزودن گره‌ای دیگر، دو گره از این مجموعه همسایه خواهند بود.

برای گراف $G$، مجموعهٔ ناوابسته بیشینه بیش‌ترین گره‌های ناهمسایهٔ این گراف را دارد و اندازهٔ این مجموعه با $\alpha (G)$ نشان داده می‌شود. هر مجموعهٔ ناوابستهٔ بیشینه‌ای مجموعه‌ای وابستهٔ بیشین نیز هست، ولی مجموعه‌ای ناوابستهٔ بیشین بایستانه (به لزوم) بیشینه نیست. یافتن مجموعهٔ ناوابستهٔ بیشینه پرسمانی ان‌پی سخت است. از این روی نمی‌توان در زمانی کوتاه چنین مجموعه‌ای را یافت.

ویژگی‌ها

پیوند با دیگر پارامون‌های گراف

مجموعه‌ای ناوابسته است اگر و تنها اگر گروهکی باشد برای اُسپُرانِ (مکمل، به انگلیسی complement) گراف. این گزاره بدین معناست که برای گراف‌هایی بزرگ که گروهک‌هایی بزرگ نداشته باشند دارای مجموعه‌های ناوابستهٔ بزرگی خواهند بود. نظریه رمزی چنین شیوه‌ای را بررسی کرده است.

مجموعه‌ای ناوابسته است اگر و تنها اگر اُسپُران این مجموعه یک پوشش گره باشد. از همین روی اندازهٔ بزرگترین مجموعهٔ ناوابسته و اندازهٔ کوچک‌ترین پوشش گره‌ای برابرند با شمار گره‌های گراف باشد.

مسئلهٔ یافتن مجموعهٔ ناوابسته

یافتن مجموعهٔ ناوابسته بیشین

مسئلهٔ یافتن یک مجموعهٔ ناوابسته بیشین را می‌توان در زمان چندجمله‌ای به کمک یک الگوریتم حریصانه حل کرد. همهٔ مجموعه‌های ناوابسته بیشین را می‌توان در زمان (O(3^n/3 یافت.

یافتن مجموعهٔ ناوابسته بیشینه

مجموعهٔ ناوابسته در گراف و علم کامپیوتر کاربردهای بسیاری دارد و حتی جزء دسته مسئله‌های NP-complete محسوب می‌شود. در حالت کلی و برای یک گراف دلخواه تا به حال الگوریتمی چند جمله‌ای برای یافتن مجموعه ناوابسته پیدا نشده‌است. این مسائل NP-complete قابل تبدیل به یک‌دیگر هستند. برای اولین بار این تبدیل‌ها توسط کوک انجام شد.

یافتن مجموعهٔ ناوابسته در گراف دوبخشی

برای حالت خاصی از گراف‌ها مجموعهٔ ناوابسته در زمان چند جمله‌ای قابل یافتن است. این دسته از گراف‌ها، گراف‌های دوبخشی هستند؛ به کمک الگوریتم تطابق می‌توانیم مجموعهٔ مورد نظر را پیدا کنیم.

اثبات درستی الگوریتم

G گرافی دوبخشی شامل دو بخش S۱ و S۲ است؛

• n: شمار گره‌ها G
• m: اندازهٔ تطابق بیشینه در G

لم: اندازهٔ مجموعهٔ ناوابسته بیشینه در G برابر n-m است.

برهان: برهان خلف؛ اگر مجموعهٔ ناوابستهٔ با اندازه‌ای بزرگتر از n-m وجود داشته باشد، دست‌کم دو گره که در تطابق بیشینه مجاور بودند، انتخاب شده‌اند. در نتیجه در این مجموعه یال وجود دارد. پس این مجموعه ناوابسته نیست.

الگوریتم

اما برای پیدا کردن آن ابتدا تطابق را در گراف پیدا می‌کنیم. شماری گره در تطابق آغشته می‌شوند. آن‌ها را $M_{1}$ و $M_{2}$ در نظر بگیرید که به ترتیب گره‌ها آغشته‌شده در بخش ۱ و ۲ هستند. مجموعهٔ $T1=S_{1}-M_{1}$ و $T2=S_{2}-M_{2}$ هیچ یالی به یک‌دیگر ندارند. مجموعهٔ $T1$ و $T2$ را به مجموعهٔ ناوابسته اضافه می‌کنیم. حالا از گره‌های موجود در $T1$ شروع می‌کنیم و تمام گره‌های را پیدا می‌کنیم که در بخش ۲ هستند و به وسیلهٔ مسیر M_افزایشی نتوانستیم به آنها برسیم. این مجموعه را به مجموعه ناوابسته خود اضافه می‌کنیم. حال شماری از یال‌های تطابق هستند که هیچ‌کدام از گره‌های آن یال در مجموعه ناوابسته نیامده‌اند. از این یال‌ها، آن‌هایی که در بخش ۱ هستند را انتخاب می‌کنیم. به این گونه توانسته‌ایم مجموعه‌ای بسازیم که هیچ دو گرهی از آن‌ها به هم یال ندارند (بدیهی است چرا که اگر یالی باشد آنگاه تطابق بیشینه نبوده) و از هر یال تطابق یک طرفش آمده‌است و بقیهٔ گره‌ها هم که از ابتدا در مجموعه بودند پس نمی‌توان مجموعه را بزرگتر کرد.

پیاده‌سازی با ++C

در کد زیر + نشان دهنده بخش ۱ است و - نشان دهنده بخش ۲.

# include<iostream>
# include<vector>
using namespace std;
const int H=1010;
vector<int> a[H];
int n,m,e,counter=0,match_up[H],match_down[H];
bool mark[H];

int dfs(int x){
 mark[x]=1;
 int temp;
 for(int i=0;i<(int)a[x].size();i++){
  temp=a[x][i];
  if(match_down[temp]==0){
   match_up[x]=temp;
   match_down[temp]=x;
   return 1;
  }
  if(mark[match_down[temp]]==1){
   continue;
  }
  if(dfs(match_down[temp])==1){
   match_up[x]=temp;
   match_down[temp]=x;
   return 3;
  }
 }
 return 0;
}

void read(){
 scanf("%d%d%d",&n,&m,&e);
 int _x,_y;
 for(int i=0;i<e;i++){
  scanf("%d%d",&_x,&_y);
  a[_x].push_back(_y);
 }
}
void matching(){
 for(int i=1;i<=n;i++){
  if(dfs(i)==1){
   counter++;
   memset(mark,0,sizeof mark);
  }
 }
}

void print(){
 cout<<(n+m)-counter<<endl;
 for(int i=1;i<=n;i++){
  if(match_up[i]==0){
   cout<<"+ "<<i<<endl;
  }else{
   if(mark[i]==1){
    cout<<"+ "<<i<<endl;
   }else{
    cout<<"- "<<match_up[i]<<endl;
   }
  }
 }
 for(int i=1;i<=m;i++){
  if(match_down[i]==0){
   cout<<"- "<<i<<endl;
  }
 }
}
int main(){
 read();
 matching();
 print();
 return 0;
}

جستارهای وابسته

مجموعهٔ ناوابسته یالی، مجموعه‌ای از یال‌ها است که گره مشترک ندارند. این مجموعه معمولاَ تطابق نامیده می‌شود.

منابع

• کتاب آشنایی با نظریه گراف وست
• دورهٔ المپیاد کامپیوتر ۱۷(inoi۱۷)

• en:Karp's_21_NP-complete_problems