رضا ندیمی - گروه علوم کامپیوتر- دانشکده علوم ریاضی- دانشگاه مازندران- بابلسر ایران

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

رنگ آمیزی گراف ها, رنگ آمیزی درخت ها, رنگ آمیزی همسایه- مکان یاب