این مساله از معدود مسائل الگوریتمی است که هم براش الگوریتم چندجمله‌ای پیدا نشده و هم اینکه ثابت نشده NP-Complete هست (یعنی با استفاده از این مساله نمی‌شه مسائل NP رو حل کرد).

برای اطلاعات بیشتر این صفحه رو ببینید:

مساله‌ی یک‌ریختی گراف‌ها

کدش رو میتونین با پس گرد (Backtrack) بزنین. کافیه تناظرهای یک به یک (جایگشتها) از راسهای گراف اول به گراف دوم رو یکی یکی بررسی کنید. اما برای کوچک کردن فضای جستجو (Branch & Bound) میتونید ابتدا ببینید هر راس گراف اول با چه راسهایی از گراف دوم درجه یکسان داره، در این صورت هر راس از گراف اول فقط به راسهایی از گراف دوم متناظر میشه که هم درجه باشند.

علاوه بر درجه میشه از پارامترهای دیگری هم استفاده کرد. مثلا کمترین فاصله بین هر زوج راس از هر دو گراف رو محاسبه کنین (با الگوریتم Floyd). در این صورت یک راس از گراف اول میتونه با یک راس از گراف دوم متناظر بشه اگر و تنها اگر توالی مرتب شده فواصل راس اول با سایر راسها در گراف اول برابر با توالی مرتب شده فواصل راس دوم با سایر راسها در گراف دوم باشه. راه دیگه اینه که از هر راس در هر دو گراف BFS بزنید و درجه راسهای قرار گرفته در هر لایه از BFS‌ رو محاسبه کنید، در هر لایه از BFS راسها رو بر اساس درجه مرتب کنید. نهایتا این توالی برای دو راس از دو گراف که میخوان متناظر هم بشن باید مساوی بشه.

به این ترتیب تعداد راسهایی از گراف دوم که قابل تناظر با گراف اول هستند اونقدر کوچک میشه که خیلی وقتها (به خصوص در مورد گرافهای تصادفی) انجام این عمل تناظر بسیار سریع قابل انجام هست (و همین موضوع این مساله رو مشکوک به داشتن الگوریتم چند جمله ای میکنه).

البته هنوز هم میشه الگوریتم رو بهبود داد، مثلا بعد از این که همه این جور کنترلها رو اضافه کردیم تا راسهایی از گراف دوم که قابل تناظر به هر راس از گراف اول هستند محدود بشه، تعداد راسهای قابل تناظر به هر راس از گراف اول رو بشماریم. اگر راسی از گراف اول بود که با صفر راس از گراف دوم قابل تناظر بود که این دو گراف هم ریخت نیستن. وگرنه ابتدا راسی از گراف اول رو وارد روال پس گرد کنیم که کمترین تعداد راسهای گراف دوم قابل متناظر شدن با اون هستند، و همین ترتیب کوچک به بزرگ رو در کل فرایند پس گرد اعمال کنیم (که به این روش پس گرد «محدودترین متغیر-نخست» یا Most Constrained Variable First میشه)

ضمنا وقتی در فرایند پس گرد هر راس رو متناظر با یک راس از گراف دوم میکنیم محدودیتهای جدیدی برای سایر راسها به وجود میاد: اگر $u$ از گراف اول به $v$ از گراف دوم متناظر شد، همسایه های $u$ فقط با همسایه های $v$ میتونن متناظر بشن، و غیر همسایه های $u$ فقط با غیر همسایه های $v$ که همین موضوع باعث میشه فضای جستجوی ما در طول فرایند پس گرد محدودتر هم بشه.

فک کنم فقط باید این کارو کرد چون برای اثبات یک ریختی دو تا گرافم حتمن باید یه تابع یک به یک بینشون ارایه کرد

البته با چک کردن یه چیزایی میتونی بگی همریخت نیستن ( مثلن تعداد راسا و مینیمم درجه و ماکسیمم درجه و دنباله درجه ها و .... ) ولی نمیتونی بگی هم ریختن حتمن...