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

مساله یکریختی گراف‌ها از مجموعه مسائل باز از لحاظ پیچیدگی محاسباتی است که فقط تعلق آن به کلاس np مشخص است ولی تعلق آن به p یا np-complete مشخص نیست. راه‌حل مساله در زمان چندجمله‌ای هنوز ناشناخته است و لذا زمینه برای تحقیق و ایده‌پردازی فراهم می‌باشد. از این رو الگوریتم‌های چندجمله ای برای این مساله جزو الگوریتم‌های ابتکاری محسوب می‌شوند. این مقاله به بررسی راه‌های تعیین یکریختی دو گراف متناهی با یکدیگر و ارائه یک روش ابتکاری جدید می‌پردازد. الگوریتمی پیشنهاد می‌شود که گراف ورودی را به یک رشته‌کد پرانتزی تبدیل می‌کند و سپس به جای مقایسه دو گراف رشته کدهای آن دو گراف با هم مقایسه می‌شوند و یکریختی یا عدم یکریختی میان آن‌ها تشخیص داده می‌شود. زمان اجرای این الگوریتمo(ne)i می‌باشد که در آن n تعداد راس‌های گراف و e تعداد یال‌های گراف است و در دسته الگوریتم‌های برچسب‌گذاری کانونی برای گراف‌های ساده، همبند و بدون برچسب قرار دارد. بعد از پیاده سازی این الگوریتم و بررسی نتایج آن مشخص شد که با عملکرد صحیح بیشتر از 99%، عدم یکریختی میان گراف‌های غیریکریخت به درستی تشخیص داده می‌شود.