الگوریتم حریصانه: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
Haniyeh120 (بحث | مشارکتها) |
Haniyeh120 (بحث | مشارکتها) |
||
خط ۱۳۳:
[[پرونده:Petersen graph 3-coloring.svg|بندانگشتی|چپ|یک رنگآمیزی [[گراف پترسن]] به کمک ۳ رنگ (کمترین تعداد رنگ ممکن).]]
با تعداد m رنگ داده شده، [[رأس (نظریه گراف)|رأس]]<nowiki/>های [[گراف]] باید به گونهای رنگ شوند که هیچ دو رأس مجاوری دارای رنگ مشابه نباشند. هدف رنگ کردن رأسها به شیوهای است که هیچ دو رأس مجاوری دارای رنگ مشابه نباشند. هیچ الگوریتم کارآمدی برای رنگآمیزی گراف با حداقل رنگهای ممکن وجود ندارد و این مسئله از جمله مسائل «انپی کامل» [[انپی_سخت|(NP Complete)]] محسوب میشود. «الگوریتمهای تقریبی» [[الگوریتم_تقریبی|(Approximate Algorithms)]] گوناگونی برای حل این مسئله وجود دارند، که[[رنگ_آمیزی_آزمند| رنگآمیزی حریصانه]] از جمله آنهاست. رنگآمیزی حریصانه به این صورت است که رأس اول را با رنگ اول رنگ میکنیم و همه رأسهای بعدی را با اولین رنگی که در رأسهای مجاور آن وجود نداشت رنگ میکنیم. اگر چنین رنگی وجود نداشت، رنگ جدیدی اضافه میکنیم. <ref>{{پک| K Erciyes|2018|ک=Guide to Graph Algorithms: Sequential, Parallel and Distributed|ص=362}}</ref>▼
▲با تعداد m رنگ داده شده، [[رأس (نظریه گراف)|رأس]]<nowiki/>های [[گراف]] باید به گونهای رنگ شوند که هیچ دو رأس مجاوری دارای رنگ مشابه نباشند. هدف رنگ کردن رأسها به شیوهای است که هیچ دو رأس مجاوری دارای رنگ مشابه نباشند. هیچ الگوریتم کارآمدی برای رنگآمیزی گراف با حداقل رنگهای ممکن وجود ندارد و این مسئله از جمله مسائل «انپی کامل» [[انپی_سخت|(NP Complete)]] محسوب میشود. «الگوریتمهای تقریبی» [[الگوریتم_تقریبی|(Approximate Algorithms)]] گوناگونی برای حل این مسئله وجود دارند، که[[رنگ_آمیزی_آزمند| رنگآمیزی حریصانه]] از جمله آنهاست. رنگآمیزی حریصانه به این صورت است که رأس اول را با رنگ اول رنگ میکنیم و همه رأسهای بعدی را با اولین رنگی که در رأسهای مجاور آن وجود نداشت رنگ میکنیم. اگر چنین رنگی وجود نداشت، رنگ جدیدی اضافه میکنیم. <ref>{{پک| K Erciyes|2018|ک=Guide to Graph Algorithms: Sequential, Parallel and Distributed|ص=362}}</ref>
|