الگوریتم مکاشفه ای بهبود یافته جهت مساله یکریختی گراف

مساله یکریختی گراف  (GIP) از لحاظ پیچیدگی محاسباتی یک مساله باز است. تاکنون هیچ الگوریتم قطعی با زمان اجرای چندجمله ای برای حل آن پیشنهاد نشده و روش های اکتشافی و فرا اکتشافی تنها راه حل آن بوده است. از آنجا که NP-complete بودن این مساله هنوز به اثبات نرسیده لذا این مساله را جز مسائل NP در نظر گرفته اند. در این مقاله یک الگوریتم چندجمله ای ساده اما کاربردی هم از لحاظ پیچیدگی زمانی و هم از لحاظ پیچیدگی فضا معرفی شده است که در زمان چندجمله ای، یکریختی میان گراف های همبند بدون برچسب را تشخیص می دهد. الگوریتم پیشنهادی دو تابع جهت محاسبه ی ویژگی های تمامی یال ها و برگ ها ارائه می دهد. خروجی این توابع به ازای هر گراف ورودی یک برچسب کانونی است و تشخیص یکریختی میان گراف ها با مقایسه میان برچسب ها صورت می گیرد. نتایج بدست آمده نشان می دهد که الگوریتم پیشنهادی با صحت بالاتر از ۹۹درصد یکریختی میان گراف ها را تشخیص می دهد. پیچیدگی زمانی الگوریتم  O(n^۳ ) می باشد که n برابر تعداد راس های گراف ورودی است.

کلیدواژه ها:

یکریختی گراف ، الگوریتم چندجمله ای ، الگوریتم مکاشفه ای ، برچسب گذاری کانونی