الگوريتمي ابتكاري جهت مسأله تشخيص يكريختي گراف‌ها مبتني بر دوري از مركز گراف

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