مجموعه مستقل

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
نه رأس آبی یک مجموعهٔ مستقل بیشینه را تشکیل می‌دهند.

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

مجموعهٔ مستقل ماکسیمال، مجموعه مستقلی است که اضافه کردن هر رأس دیگر به مجموعه، باعث اضافه شدن حداقل یک یال شود.

مجموعهٔ مستقل بیشینه، بزرگ‌ترین مجموعهٔ مستقل گرافی مانند G است و اندازهٔ آن با ( α (G نشان داده‌می‌شود.

مسئلهٔ یافتن مجموعهٔ مستقل[ویرایش]

یافتن مجموعهٔ مستقل ماکسیمال[ویرایش]

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

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

مجموعهٔ مستقل در گراف و علم کامپیوتر کاربردهای بسیاری دارد و حتی جزء دسته مسئله‌های 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۱۷)

[منابع برای] مطالعه بیشتر[ویرایش]