فهرست نشریات علمی دسترسی آزاد ایران

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