الگوریتم رنگ آمیزی آزمند

== مرتب سازی رئوس ==

معمولا الگوریتم رنگ آمیزی آزمند، بدترین عملکرد خود را بر روی گراف‌های کامل دوبخشی k n,n دارد که یال نظیر رئوس xi و xj که i=j حذف شده‌اند.{{سخ}}

 

در صورتیکه پس از شماره گذاری رئوس، دو راسی که در  یک یال حذف شده قرار دارند به صورت متوالی شماره گذاری شوند، چنین گرافی  با n رنگ، رنگ آمیزی میشود درحالیکه یک گراف ۲-رنگ پذیر است. بنابراین ترتیب رئوس در الگوریتم آزمند اهمیت فراوانی دارد.

 

[[پرونده:Graphgreedy.jpg|چپ|قاب|دو الگوریتم آزمند با ترتیب رئوس متفاوت بر روی یک گراف]]

 

یکی از روش‌های معمول شماره گذاری رئوس، انتساب کمترین اولویت به راس با کمترین درجه و مرتب سازی بقیه رئوس به همین شکل است. اگر هر زیرگراف یک گراف دارای بیشینه درجه d باشد الگوریتم حریصانه حداکثر از d+۱ رنگ استفاده می‌کند.{{سخ}}

 

برای گرافی با بیشینه درجه D الگوریتم حریصانه از حداکثر D+۱ رنگ استفاده می‌کند. [[قضیه بروک]]Brooks' theorem نشان می‌دهد این تعداد با دو استثنا (گراف‌های cliques,   odd cycle ) حداکثر برابر D است. یکی از روش‌های اثبات این نظریه، شماره گذاری رئوس به صورتیست که دو راس اول، مجاور راس نهایی بوده ولی با یکدیگر مجاور نباشند بنابراین تعداد رنگ‌های استفاده شده الگوریتم آزمند برابر D خواهد بود.

پاسخ به این سوال که آیا برای گراف مفروض G وعدد مفروض K یک الگوریتم آزمند وجود دارد که گراف را با کمتر از K رنگ، رنگ آمیزی کند یا خیر یک [[مسئله برابری پی و ان‌پی|مسئله NP-Complete]] است.{{سخ}}

 

تعدادی از معروف ترین الگوریتم‌های شماره گذاری رئوس عبارتند از:{{سخ}}

 

ترتیب خاص از پیش تعیین شده (SPECIFIC-PREDEFINED-ORDERING:SP){{سخ}}

 

ترتیب کاهش درجه نودها (DECREASING DEGREE ORDERING: DD) به عبارت دیگر هر بار راس رنگ نشده با بزرگترین درجه{{سخ}}

 

ترتیب افزایش درجه نودها(INCREASING DEGREE ORDERING: ID) به عبارت دیگر هر بار راس رنگ نشده با کوچکترین درجه{{سخ}}

 

ترتیب درجه اشباع  نودها (SATURATION DEGREE ORDERING:SD) که درجه اشباع یک نود عبارتست از تعداد رنگ‌های به کار رفته در رنگ آمیزی نودهای مجاورشمرتب سازی رنگ‌ها

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

از معروف ترین الگوریتم های حریصانه مرتب سازی رنگ‌ها عبارتند از:

SIMPLE-SEARCH-GREEDY:SSG: این روش کلاس‌های رنگ را بر اساس یک ترتیب از پیش تعریف شده انتخاب می‌کند.

LARGEST-FIRST-SEARCH-GREEDY:LFSG : کلاس‌های رنگ را بر اساس سایزشان(تعداد نودهای موجود در هر یک) به ترتیب نزولی مرتب کرده از بینشان انتخاب می‌کند. بنابراین، این روش متمایل به ایجاد کلاس‌های رنگ با بزرگترین سایز است.

SMALLEST-FIRST-SEARCH-GREEDY:SFSG : کلاس‌های رنگ را بر اساس سایز آنها به ترتیب صعودی مرتب می‌کند. بنابراین این روش متمایل به تراز کردن و توزیع یکنواخت نودها در بین کلاس‌های رنگ می‌باشد.

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

گراف کاملا ترتیب پذیر

گراف G را کاملا ترتیب پذیر[۲] می‌گوییم اگر ترتیب π وجود داشته باشد به صورتیکه با اعمال این ترتیب بر روی هر زیرگراف از گراف مفروض، الگوریتم آزمند و الگوریتم بهینه رنگ آمیزی، یکسان عمل کنند. بوسیله این ترتیب هیچ چهار راس aوbوcوd وجود ندارد که اگر در یک مسیر قرار داشته باشند راس a قبل از راس b و نیز راس c بعد از راس d قرار بگیرد. گراف‌های کاملا ترتیب پذیر زیرمجموعه‌ای از گراف‌های کامل هستند اما تشخیص چنین گرافی یک مسئله ان‌پی-کامل [۳] می‌باشد.

مجموعه‌های مختلفی از گراف‌های کاملا ترتیب پذیر شناخته شده‌است برای مثال یک گراف مقایسه پذیر[۴]، کاملا ترتیب پذیر می‌باشد به این صورت که ترتیب رئوس آن بوسیله مرتب سازی توپولوژیک[۵] تعیین می‌شود.

با سلام
درباره مسئله رنگ آمیزی گراف یک مقاله جالب پیدا کردم ، گذاشتم تا بقیه دوستان هم از اون استفاده کنند .


عنوان : رنگ آمیزی گراف

تعریف مسئله : می خواهیم در یک گراف همه گره ها را بگونه ای رنگ آمیزی کنیم که هیچ دو گره مجاوری یک رنگ نباشند ضمن اینکه کمترین رنگ را به کار برده باشیم ، پیدا کردن کمترین تعداد رنگ برای مسئله رنگ آمیزی گراف جز دسته NP-Hard است.

کاربرد مسئله : امروزه کاربرد های ساده از این مسئله در 1- مدارات الکتریکی و 2- رنگ آمیزی نقشه های جغرافیایی و غیره می باشد .

توضیح :
1# : اگر x تعداد حداقل رنگ مورد نیاز جهت رنگ آمیزی یک گراف باشد بطوریکه دارای شروط لازم در تعریف مسئله باشد (همه گره ها رنگ آمیزی شده باشند و هیچ دو گره مجاوری دارای یک رنگ نباشند) آنگاه به گراف مذکور x-Color گفته می شود

#2 : معمولا به هر گره یک نام که بیان کننده رنگی خاص می باشد اتلاق می گردد (ما در این مقاله از اعداد به این منظور استفاده کرده ایم ، بطور مثال شماره 1 را جهت رنگ آبی و 2 را جهت رنگ سبز و . . . استفاده کرده ایم)

#3 : منظور از گره مجاور در یک گراف ، دو گره می باشند که از طریق یک یال مشترک به یکدیگر متصل باشند . و کلیه مقررات مربوط به گرافها نیز در مسئله لحاظ می شود

نکات جالب مسئله :
هدف مسئله پیدا کردن حداقل رنگ برای گراف اینچنینی می باشد اما این مسئله جزء یکی از مسائل سمبلیک دنیای کامپیوتر می باشد و به دنبال راه حل هایی برای مسائل دارای محدودیت می باشد . از طرفی می توان به این مسئله از بعدی دیگر نگریست و آن اینست که یک گراف مانند G را آیا می توان با K رنگ ، رنگ آمیزی کرد ؟
به هر حال واضح است در دنیای الگوریتم های کامپیوتری با محدودیتهای زیادی مواجه هستیم که این گونه مسائل را می تواند ایجاد نماید . از آن جمله به مسائل بسیار زیادی که در سیستم عامل ها مطرح می شود می توان اشاره کرد .

ارائه یک راهکار برای حل مسئله فوق

با فرض آنکه یک گراف n عضوی داریم ماتریس مجاورت آن را چنانکه همه یالها بدون جهت فرض شده اند تشکیل می دهیم . مقادیر مثلث بالایی ماتریس از کاربر دریافت می شود چنانکه به ازای وجود یال مقدار یک و در غیر اینصورت مقدار صفر می پذیرد(مشابه فوق مقدار دهی کنید) اگر عدد غیر از این اعداد به برنامه داده شود با احتمال زیاد برنامه کارش را به درستی انجام نمی دهد و همچنین چنانچه گراف غیر همبند باشد در بیشتر موارد پاسخ صحیح نمی باشد (مگر در موارد خاص) . در نهایت کاربر بایستی داده های ورودی را صحیح وارد نماید مراحل دریافت اعداد برای یک گراف 3 عضوی در ادامه نمایش داده شده است .

[1,2] = 1
[1,3] = 1
[1,4] = 0
[2,3] = 1
[2,4] = 0
[3,4] = 1

آنچه در این الگوریتم صورت می گیرد به طور کلی بدین صورت است که فرض کنیم اندیس های ماتریس مجاورت، متناظر با گره های گرافمان باشد در این حالت اگر از گره A به گره B مسیر باشد آنگاه مختصات مربوط به A,B در ماتریس مجاورت ، مقدار یک خواهد داشت و لاغیر
A B C D
A 0 1 1 0
B ... 0 ... ...
C ... ... 0 ...
D ... ... ... 0

، بنابراین بررسی کرده ایم که از گره ای مثل A به کدام گره ها مسیر موجود است بنابراین بعد از این هیچیک از آن گره ها حق ندارند رنگ A را بپذیرند پس به سراغ گره B رفته و الی آخر . کار آرایه دوبعدی Deadline همین است که همه گره هایی را که به هر گره در ارتباط هستند را ذخیره نماید بطور نمونه از شکل مفابل می توان نتیجه گرفت B,C با گره A در ارتباطند و D ارتباطی با گره A ندارد پس می توان نتیجه گرفت B,C نمی توانند ( الزاماً ) هم رنگ A باشند ولی D می تواند ( ترجیحاً ) هم رنگ A باشد - در اینجاست که اگر از مفاهیم مجموعه ها استفاده کنیم می توانیم سادگی و گویایی الگوریتم و نهایتاً زمان اجرای آن را بهبود بخشیم ـ سپس بررسی می کنیم برای گره ای مثل x چه اتصالهایی برقرار است در نتیجه رنگ آن گره های متصل را نمی تواند بپذیرد ، بنابراین اولین رنگ امکان پذیر بعدی را می پذیرد حال ممکن است رنگی موجود نباشد و مجبور شویم یک رنگ اضافه نماییم ، در این الگوریتم این کار(انتخاب رنگ) با شماره اعداد انجام می شود در انتها رنگ انتخابی توسط زیر روال Select_color در آرایه ای به نام color و در خانه متناظر با آن گره ذخیره می شود همچنین آرایه دوبعدی Matrix به عنوان ماتریس مجاورت در این الگوریتم در نظر گرفته شده است ، آرایه دیگری به نام Last موجود است که که در واقع اشاره گری است به آخرین عنصر از آرایه Deadline به منظور ذخیره سازی عنصر بعدی در مکان مناسب .

در پیاده سازی این الگوریتم زیر تابعی به نام Select_color وجود دارد که رنگ مناسب را به گره در حال پردازش نسبت می دهد این کار با توجه به رنگهای انتساب داده شده صورت می گیرد.

 کد برنامه به شرح زیر است.


Program Coloring_Graph;

uses Crt,Graph;

Type rec= Record
x: integer;
y: integer;
end;

var
Matrix : Array [1..10,1..10] of Byte;
Deadline : Array [1..10,1..10] of Byte;
Colors : Array [1..10] of Byte;
Last: Array [1..10] of Byte;
Locat:Array [1..10] of Rec;
i,j,n : integer;

{************************************************* ******************}
Procedure Drawing;
var
Gd, Gm,clr: Integer;
begin
Gd := Detect;
InitGraph(Gd, Gm, '');
if GraphResult <> grOk then
Halt(1);

setfillstyle(1,8);
bar(350,30,570,160);
setcolor(7);
Rectangle(350,30,570,160);
line(350,55,570,55);
setcolor(15);

Locat[1].x:=50; Locat[1].y:=100;
Locat[2].x:=100; Locat[2].y:=50;
Locat[3].x:=150; Locat[3].y:=50;
Locat[4].x:=200; Locat[4].y:=100;
Locat[5].x:=200; Locat[5].y:=150;
Locat[6].x:=150; Locat[6].y:=200;
Locat[7].x:=100; Locat[7].y:=200;
Locat[8].x:=50; Locat[8].y:=150;

setcolor(14);
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if Matrix[i,j]<> 0 then
Line(locat[i].x,locat[i].y,locat[j].x,locat[j].y);
end;

for i:=1 to n do
begin
if (colors[i]>=3)
then clr:=colors[i]+1 else clr:=colors[i];
setcolor(15);
SetFillStyle(1,clr);
fillEllipse(locat[i].x,locat[i].y,10,10);
end;

setcolor(15);
for i:=1 to n do
OutTextXY(locat[i].x-2,locat[i].y-3,char(64+i));

Readkey;
CloseGraph;
end;
{************************************************* *******************}
Procedure Select_color( p,index:byte);
var i,j:integer;
begin
for i:=1 to n do
begin
for j:=1 to n do
if deadline[j,p]=i then break;
if j=n then
begin
Colors[p]:=i;
deadline[index,p]:= Colors[p];
last[p]:=last[p] + 1;
break;
end;
end;
end;
{
************************************************** ***************
* s t a r t p r o g r a m *
************************************************** ***************
}
Begin
clrscr;
write('please set size of matrix [ n<8 !] : ');
readln(n);

if n>8 then halt;
for i:=1 to n do
last[i]:=1;


for i:=1 to n-1 do
for j:=i+1 to n do
begin
write('[',i,',',j,'] : ');
read(Matrix[i,j]);
Matrix[j,i]:=Matrix[i,j];
end;

for i:=1 to n do
for j:=1 to n do
begin
gotoxy(10+2*i,j+5);
Write(Matrix[i,j]);
end;

for i:=1 to n do
begin
Select_color(i,last[i]);

for j:=1 to n do
if Matrix[i,j]<>0 then
begin
Deadline[last[j],j]:=Colors[i] ;
last[j]:=last[j] + 1 ;
end;
end;

for i:=1 to n do
begin
gotoxy(10+3*i,20);
Write(Colors[i]);
end;

Readkey;
Drawing;
End

مطالب مشابه :

دانلود پایان نامه رنگ آمیزی گراف با الگوریتم ژنتیک

رنگ آمیزی گراف با الگوریتم گراف با الگوریتم ژنتیک. رنگ آمیزی گراف ان

---

الگوریتم رنگ آمیزی آزمند

معمولا الگوریتم رنگ آمیزی آزمند دارد که گراف را با کمتر از k رنگ، رنگ الگوریتم ژنتیک.

---

كاربرد گراف دررياضي گسسته

نظریه رنگ آمیزی یالی توسط گراف علم ژنتیک است که توسط گراف به الگوریتم با یک

---

کاربردهای گراف

، n با این قاعده رنگ نظریه رنگ آمیزی یالی توسط گراف گراف در علم ژنتیک

---

مقالات شبیه سازی شده رشته برق در متلب MATLAB

خوشه بندی با الگوریتم ژنتیک سال ارائه: پروژه پردازش تکاملی بر روی مسئله رنگ امیزی گراف

---

پروژه ها و مقالات شبیه سازی شده در متلب- پردازش سیگنال و هوش مصنوعی

درونیابی طرح رنگ با استفاده از با الگوریتم ژنتیک. بر روی مسئله رنگ امیزی گراف.

---

نتایج داوری مقالات

بهبود کارایی الگوریتم ژنتیک با بندی گراف وظایف ژنتیک در رنگ آمیزی گراف.

---

الگوریتم کلونی مورچگان

مثلا در گراف الگوریتم رنگ آمیزی خلاصه سازی متن بااستفاده از الگوریتم ژنتیک با

---

برچسب :
رنگ آمیزی گراف با الگوریتم ژنتیک