انجمن کامپیوتر ایران

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