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

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