نمایش نتایج 1 تا 17 از 17

نام تاپیک: درباره مسئله رنگ آمیزی گراف

  1. #1
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208

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

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


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

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

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

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

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

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

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

  2. #2
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208

    ادامه

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

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

  3. #3
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208

    برنامه

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

    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.
    آخرین ویرایش به وسیله MIDOSE : شنبه 28 آذر 1388 در 02:14 صبح

  4. #4
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208

    ادامه

    با سلام

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

    موفق باشید.
    فایل های ضمیمه فایل های ضمیمه

  5. #5
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208
    با سلام
    دوستان علاقه مند لطفا جهت اطلاع سایر اعضا کاربردهای این الگوریتم را نام ببرید .

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

  6. #6
    کاربر دائمی
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    مشهد
    پست
    173

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

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

  7. #7
    کاربر دائمی آواتار kashaneh
    تاریخ عضویت
    آبان 1383
    محل زندگی
    در همین نزدیکی
    پست
    537

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

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

  8. #8
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208

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

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


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

    سربلند باشید.
    آخرین ویرایش به وسیله raha_hakhamanesh : چهارشنبه 31 تیر 1388 در 12:42 عصر

  9. #9
    کاربر دائمی آواتار kashaneh
    تاریخ عضویت
    آبان 1383
    محل زندگی
    در همین نزدیکی
    پست
    537

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

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

  10. #10
    کاربر جدید
    تاریخ عضویت
    آذر 1388
    محل زندگی
    ویلاشهر
    پست
    4

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

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

  11. #11
    کاربر دائمی
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    مشهد
    پست
    173

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

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

  12. #12

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

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


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

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

  13. #13

    نقل قول: ادامه

    نقل قول نوشته شده توسط raha_hakhamanesh مشاهده تاپیک
    با سلام

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

    موفق باشید.


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

  14. #14

    Cool نقل قول: درباره مسئله رنگ آمیزی گراف

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

  15. #15

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

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

  16. #16

    نقل قول: برنامه

    نقل قول نوشته شده توسط 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.
    سلام ببخشید میشه این را فایل اجراییش را بگذارید؟
    اگر ممکنه بگید از چه الگوریتمی استفاده شده و نحوه ی کار با فایل اجرایی هم بگید لطفا

  17. #17

    نقل قول: ادامه

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

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •