مجموعه مستقل

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

مجموعه مستقل (به انگلیسی: Independent Set)، برای یک گراف مجموعه‌ای از گره‌ها‌ست که هیچ یالی میان هیچ جفتی از این گره‌ها نباشد.

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

برای گراف $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