الگوریتمی برای ‌رنگ‌آمیزی همسایه- مکان‌یاب ‌درخت‌ها

در این مقاله، الگوریتمی برای ‌رنگ‌آمیزی همسایه- ‌مکان‌یاب ‌درخت‌ها  ارایه گردیده است. ‌رنگ‌آمیزی ‌گراف‌ها و کاربردهای آن از مباحث اصلی و پر کاربرد ‌گراف‌هاست. ‌رنگ‌آمیزی ‌گراف‌ها در دو حوزه ‌رنگ‌آمیزی گره‌ها و ‌رنگ‌آمیزی ‌یال‌های گراف مورد مطالعه قرار گرفته اند. در ‌رنگ‌آمیزی گره‌ها، در سال‌های اخیر مفاهیم جدیدی از ‌رنگ‌آمیزی ‌گراف‌ها مانند &‌رنگ‌آمیزی ‌مکان‌یاب& و & ‌رنگ‌آمیزی همسایه- ‌مکان‌یاب&، مطرح شده و مورد مطالعه قرار گرفته‌اند. تخصیص اعضای مجموعه رنگ  c={c1, c2, …, ck} به مجموعه گره‌های یک گراف را یک k- رنگ آمیزی (مناسب) گوییم اگر و فقط اگر به هیچ زوج همسایه‌ای رنگ یکسان اختصاص نیافته باشد. با اعمال ‌محدودیت‌های بیشتر در رنگ‌آمیزی، به انواع دیگری از این مسئله خواهیم رسید. تعداد حداقل رنگ برای ‌رنگ‌آمیزی مناسب یک گراف را عدد رنگی گراف گوییم؛ این عدد برای انواع ‌رنگ‌آمیزی به طور مشابهی تعریف می‌شود. پیدا کردن عدد رنگی یک گراف در فرم بهینه‌سازی مسئله و همچنین تشخیص k-رنگ پذیری گراف برای k>2، در فرم تصمیم مسئله، از مسایل معروف np-hard هستند. نوع خاصی از ‌رنگ‌آمیزی مناسب که موضوع این مقاله است، ‌رنگ‌آمیزی همسایه- ‌مکان‌یاب گره‌ها است. در این مسئله گره‌ها باید طوری ‌رنگ‌آمیزی شوند که علاوه بر غیر یکسان بودن رنگ همسایه‌ها، مجموعه رنگ همسایه‌های ‌گره‌های همرنگ، متمایز از هم باشند. در مبحث ‌رنگ‌آمیزی همسایه- ‌مکان‌یاب گره‌ها با وجود مطالعات وسیع صورت گرفته در زوایای نظری بحث، از جمله روابط بین عدد رنگی در انواع رنگ‌آمیزی‌ها و عدد رنگی ‌گراف‌های خاص، از نظر الگوریتمی، در این زمینه نتیجه قابل توجهی وجود ندارد. در این مقاله، الگوریتمی برای ‌رنگ‌آمیزی همسایه- ‌مکان‌یاب ‌درخت‌ها ارایه شده است. ثابت می‌کنیم الگوریتم از مرتبه زمانی چند جمله‌ای است و در مورد حداکثر ‌رنگ‌های استفاده شده برای ‌حالت‌های خاصی از ‌درخت‌ها بحث خواهیم کرد.