المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:تطابق و مجموعه‌‌ی مستقل بیشینه در درخت

تطابق و مجموعه‌‌ی مستقل بیشینه در درخت

تعریف مسئله

یک درخت $n$ راسی به شما داده شده است ، از شما خواسته می‌شود که یک تطابق و یک مجموعه‌ی مستقل بیشینه‌ی آن را بیابید.

الگوریتم

برای یافتن تطابق بیشینه از الگوریتم زیر استفاده می‌کنیم:

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

برای یافتن مجموعه مستقل بیشینه می‌توان مجموعه مستقلی با استفاده از تطابق بالا یافت(در گراف های دو بخشی این کار ممکن است)

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

اثبات درستی

برای هر برگ خاص (برای مثال $v$) در یک درخت دلخواه یک تطابق بیشینه وجود دارد به صورتی که یال متناظر با $v$ درون تطابق بیشینه باشد. برای ساخت چنین تطابق بیشینه‌ای ، کافیست یک تطابق بیشینه‌ی دلخواه در نظر گرفته و زوج راس مجاور $v$ را به $v$ تغییر دهیم. در صورتی که راس مجاور $v$ از قبل با راس دیگری زوج نشده باشد اندازه‌ی تطابق بیشتر می‌شود وگر نه اندازه‌ی آن تغییری نمی‌کند. پس این تطابق نیز بیشینه است.

از آن‌ جا که در هر تطابق بیشینه ، با حذف $2$ راس مجاور آن از تطابق و گراف همچنان یک تطابق بیشینه باقی می‌ماند، به استقرا بر روی تعداد راس های درخت اثبات می‌شود الگوریتم حریصانه‌ی حذف برگ و راس مجاور آن تطابق بیشینه را می‌یابد.

مشابه الگوریتم حریصانه‌ی تطابق ثابت می‌شود الگوریتم دوم نیز مقدار بیشینه‌ی مجموعه مستقل را می‌یابد.

پیچیدگی‌ الگوریتم

با استفاده از پیمایش DFS برای پیاده سازی پیچیدگی این الگوریتم از $O(n)$ است.

پیاده‌سازی اولیه

گر چه پیاده سازی این الگوریتم توسط پیمایش DFS رایج تر و کوتاه تر است ، اما کد زیر با همان پیچیدگی این کار را انجام می دهد ، در عین حال به شکل تئوری الگوریتم شباهت بیشتری دارد.

کد زیر برگ ها و راس های درجه $0$ درخت را در یک صف نگه داری می‌کند و در هر مرحله اولین راسی که حذف نشده از این صف را به مجموعه مستقل اضافه می کند و آن را حذف می‌کند ، در صورتی که آن راس برگ باشد آن را به تطابق اضافه کرده و راس مجاور آن را نیز حذف می‌کند.

A.cpp
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
const int maxn = 100*1000+100;
int n;
 
vector<int> independent;
vector<pair<int,int> > matching;
vector<int> adj[maxn];
queue<int> q;
 
bool mark[maxn];
int degree[maxn];
 
void remove(int v){
	mark[v]=true;
	for(int i = 0 ; i < adj[v].size() ; ++i){
		degree[adj[v][i]]--;
		if(degree[adj[v][i]]<=1)
			if(!mark[adj[v][i]])
				q.push(adj[v][i]);
	}
}
 
int main(){
 
	cin >> n;
	for(int i = 0 ; i < n-1 ; ++i){
		int v , u;
		cin >> v >> u;
		v--;u--;  	// 0 based index
		adj[v].push_back(u);
		adj[u].push_back(v);
		degree[v]++;
		degree[u]++;
	} 	
 
        for(int i = 0 ; i < n ; ++i)                                        // برگ های درخت را به صف اضافه کن   
	    if(degree[i] <= 1)
		q.push(i);
 
  	while(!q.empty()){
	    int v = q.front();
	    q.pop();
	    if(mark[v])
		    continue;
	    independent.push_back(v); 
  	    if(degree[v]==1)                                                // در صورتی که این راس یک همسایه حذف نشده داشته باشد
	    {
 		    for(int i=0; i < adj[v].size() ; ++i) 
		    	if(!mark[adj[v][i]])                                // آن را پیدا کن
			{
 			    matching.push_back(pair<int,int>(v,adj[v][i])); // یال بین آن دو را به مچینگ اضافه کن
			    remove(adj[v][i]);
			    break;
			}
 
	    }
	    remove(v);
	}  
 
 
	cout << "Independent set: " ;
	for(int i = 0 ; i < independent.size() ; ++i)
		cout << independent[i]+1 << " " ;
        cout << endl;
 
	cout << "Matching: " ;
	for(int i = 0 ; i < matching.size() ; ++i)
		cout << "(" << matching[i].first+1 << "," << matching[i].second+1 << ") ";
        cout << endl; 
 
        return 0;
}  

پیاده‌سازی دوم

B.cpp
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
const int maxn = 100*1000+100;
int n;
 
vector<int> independent;
vector<pair<int,int> > matching;
vector<int> adj[maxn];
queue<int> q;
 
bool mark[maxn];
bool markInd[maxn];
 
void dfs(int v){
	mark[v]=true;
	int u=-1;
	for(int i = 0 ; i < adj[v].size() ; ++i)
		if(!mark[adj[v][i]]){
			dfs(adj[v][i]);
			if(markInd[adj[v][i]])
				u=adj[v][i];
		}
	if(u==-1){
		markInd[v]=true;
		independent.push_back(v);
	}else{
		matching.push_back(pair<int,int>(v,u));
	}
}
 
int main(){
 
 	cin >> n;
	for(int i = 0 ; i < n-1 ; ++i){
		int v , u;
		cin >> v >> u;
		v--;u--;  	// 0 based index
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
 
	dfs(0);
 
	cout << "Independent set: " ;
	for(int i = 0 ; i < independent.size() ; ++i)
		cout << independent[i]+1 << " " ;
        cout << endl;
 
	cout << "Matching: " ;
	for(int i = 0 ; i < matching.size() ; ++i)
		cout << "(" << matching[i].first+1 << "," << matching[i].second+1 << ") ";
        cout << endl;      
 
        return 0;
}

کابردها

مثال: صورت مسئله اینجا می‌آید.

پاسخ

پاسخ مسئله اینجا می‌آید

مسائل نمونه

مراجع


ابزار صفحه