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


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

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

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

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

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

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

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