درباره مسئله رنگ آمیزی گراف

[raha_hakhamanesh]

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


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

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

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

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

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

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

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

[raha_hakhamanesh]

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

با فرض آنکه یک گراف 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 وجود دارد که رنگ مناسب را به گره در حال پردازش نسبت می دهد این کار با توجه به رنگهای انتساب داده شده صورت می گیرد.

[raha_hakhamanesh]

شبه کد این برنامه رو آقای جم پور(ارائه کننده مقاله) برای بنده ارسال کرده که متاسفانه دچار مشکل شده بود ولی کد برنامه به شرح زیر است.


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.

[raha_hakhamanesh]

با سلام

این هم از PDF برنامه و توضیحات کامل درباره این مسئله .

موفق باشید.

[raha_hakhamanesh]

با سلام
دوستان علاقه مند لطفا جهت اطلاع سایر اعضا کاربردهای این الگوریتم را نام ببرید .

1- رنگ آمیزی نقشه های جغرافیایی
2- . . .

[mehran5]

سلام ممنون ا زمطالب مفیدتون .میخواستم بودنم کد بالا چه زبونیه و از کدام الگوریتم استفاده شده ممنون؟

[kashaneh]

با سلام... آیا الگوریتمی که در مورد این مسئله در اینجا گفته شده، یک روش حل به روش حریصانه هست یا خیر (چه روشی است؟)؟ اساتید راهنمایی کنن... با تشکر

[raha_hakhamanesh]

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


1- الگوریتم ارائه شده به زبان پاسکال نوشته شده بود.
2- این الگوریتم یک تکنیک برنامه نویسی پویا است (D.P) که از پیچیدگی محاسباتی خوبی برخوردارمی باشد.

سربلند باشید.

[kashaneh]

دوست عزیز... من از شما این سوال را کردم که آیا این الگوریتم پیشنهادی در اینجا از نوع حریصانه هست یا خیر؟ اما شما می گویید بله برنامه نویسی پویاست!!؟ به نظر من اینکه شما اصرار به این دارید تا یک رنگ را تحت شرایط مختلف یه یک گراف اختصاص دهید، نوعی پیاده سازی حریصانه است... آیا توجیح مناسب و بیشتری برای اینکه این الگوریتم برنامه نویسی پویاست دارید؟ متشکرم

[mina.sarvi]

سلام به همگی این یک مسله back tracking و با این روش حل می شه

[mehran5]

سلام دوستان من به سه چهار روش مسله حل کردم
متاسفانه چون کدشو از دست دادم حالشو ندارم از صفر شروع کنم ولی همینو از استادگرفتم بازم غنیمته؟!

[saman_itc]

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


1- الگوریتم ارائه شده به زبان پاسکال نوشته شده بود.
2- این الگوریتم یک تکنیک برنامه نویسی پویا است (D.P) که از پیچیدگی محاسباتی خوبی برخوردارمی باشد.

سربلند باشید.
کد قابل اجرای آن رو هم دارید؟

[negarfke]

با سلام

این هم از PDF برنامه و توضیحات کامل درباره این مسئله .

موفق باشید.



با تشکر از شما
خواهش می کنم سورس کد رنگ آمیزی گراف رو با زبان vb یا ++c برای دانلود قرار بدین
خیلی ضروریه

[morteza_bn]

سلام دوستان من به سه چهار روش مسله حل کردم
متاسفانه چون کدشو از دست دادم حالشو ندارم از صفر شروع کنم ولی همینو از استادگرفتم بازم غنیمته؟!

آخه عزیز من فایل اگزه رو گذاشتی که چی بشه...:عصبانی++:
اینجا همه دنبال سورس کد هستن
اگه تونستی کدشو بذار

[matmatin]

سلام دوستان من به سه چهار روش مسله حل کردم
متاسفانه چون کدشو از دست دادم حالشو ندارم از صفر شروع کنم ولی همینو از استادگرفتم بازم غنیمته؟!

سلام ببخشید میشه روش کار با این نرم افزارتون را بگید؟

[matmatin]

شبه کد این برنامه رو آقای جم پور(ارائه کننده مقاله) برای بنده ارسال کرده که متاسفانه دچار مشکل شده بود ولی کد برنامه به شرح زیر است.


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.

سلام ببخشید میشه این را فایل اجراییش را بگذارید؟
اگر ممکنه بگید از چه الگوریتمی استفاده شده و نحوه ی کار با فایل اجرایی هم بگید لطفا

[mohammadsibo]

دست شما درد نکنه.واقعا" مفید بود و استفاده کردم.ممنون