مجموعه مستقل

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

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

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

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

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

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

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

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

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

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

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

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

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

الگوریتم

اما برای پیدا کردن آن ابتدا تطابق را در گراف پیدا می‌کنیم. شماری گره در تطابق آغشته می‌شوند. آن‌ها را ${\displaystyle M_1}$

پیاده‌سازی با ++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۱۷)