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

مسأله یکریختی گراف‌ها از مجموعه مسائل باز از لحاظ پیچیدگی محاسباتی است که فقط تعلق آن به کلاس NP مشخص است ولی تعلق آن به P یا NP-Complete مشخص نیست. راه‌حل مسأله در زمان چندجمله‌ای هنوز ناشناخته است و لذا زمینه برای تحقیق و ایده‌پردازی فراهم می‌باشد. از این رو الگوریتم‌های چندجمله­ای برای این مسأله جزو الگوریتم‌های ابتکاری محسوب می‌شوند. این مقاله به بررسی راه‌های تعیین یکریختی دو گراف متناهی با یکدیگر و ارائه یک روش ابتکاری جدید می‌پردازد. الگوریتمی پیشنهاد می‌شود که گراف ورودی را به یک رشته‌کد پرانتزی تبدیل می‌کند و سپس به جای مقایسه دو گراف رشته­ کدهای آن دو گراف با هم مقایسه می‌شوند و یکریختی یا عدم یکریختی میان آن‌ها تشخیص داده می‌شود. زمان اجرای این الگوریتمO(ne)i می‌باشد که در آن n تعداد رأس‌های گراف و e تعداد یال‌های گراف است و در دسته الگوریتم‌های "برچسب‌گذاری کانونی" برای گراف‌های "ساده، همبند و بدون برچسب" قرار دارد. بعد از پیاده­سازی این الگوریتم و بررسی نتایج آن مشخص شد که با عملکرد صحیح بیشتر از 99%، عدم یکریختی میان گراف‌های غیریکریخت به درستی تشخیص داده می‌شود.