ریاضیات

اگرچه پریدن به آن کاغذ بعد از مقالات قبلی کمی جهش است.
خوب، پس اکنون همه شما گرم شده اید. در واقع شما احتمالا آنقدر سرحال هستید که فکر می کنید یک الگوریتم کلاسیک زمان چند جمله ای درست در گوشه و کنار است. وقت آن است که در آن افکار دمی بگذاریم.
ابتدا اجازه دهید با مقاله ای شروع کنیم که در حال حاضر بهترین الگوریتم برای نمودارهای عمومی است. خوب در واقع برای بهترین الگوریتم اصلی، مطمئن نیستم که مقاله واقعی وجود دارد یا خیر، اما مقاله ای وجود دارد که به کران مشابهی می رسد.

• "برچسب گذاری متعارف نمودار" توسط لازلو بابای و یوجین ام. لوکس STOC 1983 

این یک زیرنمایی را توصیف می کند (یا، اشتباه، اسکات تصمیم گرفت این را چه نامی بگذارد ؟)، الگوریتم زمان برای یک نمودار بارگه ها. در حال حاضر به عنوان یک لیست خواندن، من هنوز ورود به این مقاله را به طور کامل توصیه نمی کنم، اما فقط می خواستم خوش بینی شما را برای یک الگوریتم کلاسیک با نشان دادن به شما کم کنم (الف) بهترین چیزی که ما به طور کلی داریم یک الگوریتم زمانی نیمه نمایی است، (ب) این رکورد برای نزدیک به سه دهه باقی مانده است، و (ج) که اگر به مقاله نگاه کنید می توانید ببینید که کار آسانی نیست. همه کسانی که وارد می شوند امید را رها کنید؟
بسیار خوب، پس ظاهراً شما ناامید نشده اید، بنابراین به جلو فشار می آورید. خب بعد چی بخونم؟
خوب یک استراتژی این است که فهرست تمام نمودارهایی را که الگوریتم های شناخته شده کارآمدی برای آنها وجود دارد مرور کنید. این یک لیست کاملاً است، و اگر حداقل یکی از این موارد را مجدداً حل نکنید، حداقل کسب دانش در مورد این مقالات مفید است (در بالا به مقاله برای تعدد مقادیر ویژه محدود اشاره کردیم):

• نمودارهای مسطح: "الگوریتم زمان خطی برای هم ریختی نمودارهای مسطح" توسط JE Hopcroft و JK Wong، STOC 1974 ( مقاله در اینجا )
• یا به طور کلی نمودارهای جنس محدود: "آزمایش ایزومورفیسم برای نمودارهای جنس محدود" توسط گری میلر، STOC 1980 ( مقاله در اینجا )
• نمودارها با درجه محدود: "ایزومورفیسم نمودارهای ظرفیت محدود را می توان در زمان چند جمله ای آزمایش کرد" توسط یوجین ام. لوکس، مجله علوم کامپیوتر و سیستم 25: 42-65، 1982 ( مقاله در اینجا )

در امتداد یک رگه مشابه، یک الگوریتم زمانی زیر نمایی برای نمودارهای به شدت منظم وجود دارد که بهتر از بهترین الگوریتم کلی است که در بالا توضیح داده شد:

• "تست سریعتر ایزومورفیسم نمودارهای با قاعده قوی" توسط Daniel A. Spielman STOC 1996 (مقاله در اینجا)

در این مرحله، احتمالاً شما بیش از حد بار شده اید، بنابراین یک کار خوب در هنگام بارگیری بیش از حد، پیدا کردن یک کتاب است. یک کتاب جالب این است

• «الگوریتم‌های نظری گروهی و ایزومورفیسم نمودار» توسط CM Hoffman 1982 

همانطور که می بینید این مقاله قبل از معرفی بهترین الگوریتم ها نوشته شده است. با این حال، این کتاب نسبتاً خواندنی است و شروع به تنظیم نظریه گروهی می کند که اگر می خواهید مقالات بعدی را فتح کنید، به آن نیاز دارید. کتاب دیگری با نتایج خوبی است

• "مسئله ایزومورفیسم گراف: پیچیدگی ساختاری آن" توسط یوهانس کوبلر، اووه شونینگ، یاکوبو توران (1993) 

که در آن شما برخی از نتایج خوب نظریه پیچیدگی پایه را در مورد ایزومورفیسم گراف پیدا خواهید کرد.
خوب حالا که رفته اید و شروع به یادگیری در مورد برخی پیچیدگی های محاسباتی در رابطه با هم ریختی گراف کرده اید، احتمالا زمان خوبی برای توقف و بررسی الگوریتم های عملی واقعی برای ایزومورفیسم گراف است. پادشاه تپه اینجا، تا جایی که من می دانم، برنامه ناوتی (بدون AUTomorphism، بله؟) توسط برندان دی. مک کی است. متأسفانه به نظر می رسد که یک موتور جستجوی خاص نسبت به کلمه "شیطان" کمی سنگین است (توجه داشته باشید، هنگام نامگذاری یک بسته نرم افزاری، کلمه کلیدی مرتبط با پورن را در نظر بگیرید):

وظیفه اصلی Nauty تعیین گروه اتومورفیسم یک گراف (گروهی از جایگشت‌ها که نمایش گراف را بدون تغییر می‌گذارند) است، اما nauty یک برچسب متعارف نیز تولید می‌کند که می‌تواند برای آزمایش هم‌شکلی استفاده شود. Nauty می تواند تست های هم ریختی نمودارهای 100 راس را در حدود یک ثانیه انجام دهد. مقاله ضمیمه ای وجود دارد که نحوه عملکرد ناوتی را توضیح می دهد:

• "ایزومورفیسم نمودار عملی"، توسط برندان دی. مک کی، کنگره Numerantium، 30، 45-87، 1981. 

یک برچسب متعارف برای یک گراف تابعی از گراف ها به مجموعه ای از برچسب ها است به طوری که برای دو نمودار برچسب یکسان است اگر و فقط اگر دو نمودار هم شکل باشند. این چیزی است که nauty تولید می کند: اگر می خواهید بدانید که آیا نمودارها هم شکل هستند یا خیر، فقط فرم های متعارف این نمودارها را محاسبه کرده و نتایج را با هم مقایسه کنید. اگر شکل متعارف یکسانی داشته باشند هم شکل هستند و اگر نداشته باشند هم شکل نیستند.

که فرد را به فکر کردن در مورد سایر طرح‌های برچسب‌گذاری برای حل ایزومورفیسم گراف سوق می‌دهد. یکی از ساده‌ترین تلاش‌ها (تلاش چون کار نمی‌کند) برای ایجاد یک طرح برچسب‌گذاری متعارف، موارد زیر است: با برچسب‌گذاری رئوس دو نمودار با درجه‌شان شروع کنید. اگر این لیست را مرتب کنید و آنها لیست های مرتب شده متفاوتی هستند، پس نمودارها نمی توانند هم شکل باشند. سپس می‌توان برچسب راس را با برچسبی متشکل از چند مجموعه برچسب راس فعلی و برچسب‌های رئوس همسایه جایگزین کرد (مجموعه‌ای را فراخوانی کنید که ورودی‌ها می‌توانند چندین بار ظاهر شوند.) سپس می‌توان این چند مجموعه‌ها را از نظر واژه‌شناسی مرتب کرد و دو لیست مرتب شده را برای هر دو نمودار مقایسه کنید. دوباره اگر لیست ها یکسان نباشند، نمودارها هم شکل نیستند. اگر هنوز متوجه نشده اید که نمودارها هم شکل نیستند، می توانید ادامه دهید، اما ابتدا، برای کوچک نگه داشتن برچسب ها، باید برچسب های مرتب شده از نظر لغوی را با یک عدد صحیح کوچک که نشان دهنده ترتیب مرتب شده برچسب است جایگزین کنید. سپس می توان ساخت یک برچسب گذاری چند مجموعه ای جدید را از این برچسب گذاری های اعداد صحیح جدید تکرار کرد. این یک طرح ساده برای پیاده سازی است.

منبع

https://dabacon.org/pontiff/2010/08/04/reading-list-graph-isomorphism/