رنگ‌آمیزی گراف‌ها

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

می ‌خواهیم الگوریتمی ارائه‌دهیم که $\chi(G)$ را بیابد و در حالت کلی تر گراف را آن را با این تعداد رنگ ، رنگ‌آمیزی کند.

برای این مسئله می‌توان از روش انشعاب و حد استفاده کرد. می دانیم گراف را می‌توان با $\Delta+1$ رنگ رنگ‌آمیزی کرد پس $B=\Delta+1$ می تواند کران اولیه برای شروع جستجو باشد.

از آنجا که هیچ 2 راس مجاوری رنگ یکسان ندارند، به عبارت دیگر می‌خواهیم گراف را به $\chi(G)$ مجموعه مستقل افراز کنیم. در هر مرحله یک زیر مجموعه مستقل ماکسیمال گراف که هنوز رنگ نشده را به رنگ جدید در آورده و باقی گراف را به صورت بازگشتی رنگ می کنیم و در صورت خارج شدن از کران به دست آمده به مرحله‌ی قبل باز می‌گردیم.

از آنجا که به ازای هر ترتیب رنگ کردن این مجموعه‌ها این روش به جواب مشابه می‌رسد، می‌توانیم فرض کنیم این مجموعه ها را از بزرگ به کوچک رنگ می‌کنیم. می‌دانیم اگر بخواهیم در کمتر از B مرحله گراف را رنگ آمیزی کنیم باید طبق اصل لانه کبوتری در یک مرحله حداقل $n/B$ راس را رنگ کرده باشیم. از آنجا که ترتیب رنگ کردن از بزرگ به کوچک است، در هر مرحله باید مجموعه مستقل انتخاب شده حداقل $|V'|/B$ عضو داشته باشد ، که $V'$ مجموعه‌ی راس های رنگ نشده می باشد.

پس الگوریتم مطابق زیر عمل می‌کند:

1. تا زمانی که هنوز راس رنگ نشده‌ای وجود دارد:
2. به ازای هر مجموعه‌ی مستقل ماکسیمال گراف مثلا $\alpha$
3. در صورتی که سایز $\alpha$ بزرگ تر از مجموعه مستقل قبلی باشد، برای جلو گیری از شمردن حالت تکراری آن را ترک می‌کنیم
4. در صورتی که $|\alpha| > n/(B-k)$ آن را به رنگ $k+1$ در می‌آوریم و $k$ را یک واحد زیاد می‌کنیم
5. در غیر این صورت $\alpha$ نمی‌تواند به افراز اضافه شود و سراغ مجموعه مستقل بعدی می‌رویم

در پایان عدد $k$ نشان دهنده‌ی تعداد رنگ های استفاده شده خواهد بود.

پیچیدگی این الگوریتم $O(\Delta^n)$ است اما در صورتی که مسئله با برنامه‌نویسی پویا پیاده سازی شود، یعنی مقدار $\chi(G')$ برای هر زیر گراف القایی پس از یک بار محاسبه ذخیره شود پیچیدگی از $O(4^n)$ خواهد بود.

در کد زیر راس ها را به ترتیب رنگ می‌کنیم به طوری که کسی با هم رنگ خودش مجاور نباشد.

A.c

 
 
void bnb(int v){
	if(v==n)
	{
		if(B < k)
		{
			B=k;
			saveColoring();
		}
		return;
	}
 
	for(int i = 1 ; i <= min(k+1,B-1) ; ++i){
		isInvalid=false;
		newColor=false;
 
		for(int j=0;j < (int)adj[v].size();++j)
			if(adj[v][j] < v && color[adj[v][j]]==i){
				isInvalid=true;
			}
		if(isInvalid)
			continue;
 
		if(i==k+1)
		{
			k++;
			newColor=true;
		}
		color[v]=i;
		bnb(v+1);
		if(newColor)
			k--;
	}
}

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

B.c

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

• سوال عملی دوره‌ی تابستان ۲۴ [سطح: ساده]

• تابع اویلر - سایت ماکزیمال
• تابع اویلر - ویکی‌پدیا