ریاضیات

ارسال شده در 4 آگوست 2010 توسط dabacon

اخطار: این فهرست منحصر به فرد از مطالب خواندنی به هیچ وجه به معنای جامع بودن نیست و حتی تضمین نمی‌شود که بر مهم‌ترین مقالات مربوط به هم‌شکلی گراف تمرکز کند. پیشنهادات برای مقالات دیگر برای افزودن به لیست بسیار قدردانی می شود: نظر خود را بنویسید!

مسئله ایزومورفیسم گراف یک مسئله جالب است. گراف مجموعه ای از رئوس به همراه یال هایی است که این رئوس را به هم متصل می کنند. مسئله ایزومورفیسم گراف این است که با توجه به توصیف دو نمودار، تعیین کنیم که آیا این توصیفات واقعاً همان نمودار هستند یا خیر. به عنوان مثال، آیا می توان رئوس دو نمودار زیر را مجدداً برچسب زد و جابه جا کرد تا یکسان به نظر برسند؟

دست برداشتن از؟ خوب، خوب این یکی خیلی سخت نبود، اما بله، این نمودارها هم شکل هستند معمولاً دو تصویر از نمودارها به ما داده نمی شود، اما در عوض توضیح مختصری از این که چه رئوسی به یکدیگر متصل هستند، داده می شود. این توسط یا و ماتریس مجاورت یا و لیست مجاورت داده می شود. ماتریس مجاورت یک نمودار بارئوس است ماتریس که ورودی دهم تعداد یال های راس استبه. یک الگوریتم برای مسئله ایزومورفیسم گراف کارآمد است اگر زمان اجرای آن چند جمله ای در تعداد رئوس نمودارهای درگیر باشد.
یکی از دلایل جالب توجه هم ریختی گراف، وضعیت فعلی آن در پیچیدگی محاسباتی است. به احتمال زیاد NP-کامل نیست (زیرا این امر باعث فروپاشی سلسله مراتب چند جمله‌ای می‌شود)، اما با وجود مقدار قابل توجهی کار، هیچ الگوریتم زمان چند جمله‌ای شناخته‌شده‌ای برای این مشکل وجود ندارد. مشخص شده است که ایزومورفیسم نمودار در کلاس پیچیدگی NP intersect co-AM است، که به نوعی شبیه به جایی است که نسخه تصمیم گیری فاکتورگیری در آن قرار دارد (NP intersect co-NP.) این شباهت، همراه با این واقعیت که تعمیم طبیعی حل مسئله کوانتومی با فاکتورگیری ( مسئله زیرگروه پنهان) مربوط به ایزومورفیسم گراف است (حل کارآمد مسئله زیرگروه پنهان برای گروه متقارن، الگوریتم کارآمدی را برای ایزومورفیسم گراف به دست می دهد) به این امید منجر شده است که رایانه های کوانتومی ممکن است بتوانند به طور کارآمد ایزومورفیسم گراف را حل کنند. اعتراف می‌کنم که طی سال‌ها، من به آرامی اما مطمئناً به بیماری هم‌شکلی گراف کاملاً شدید مبتلا شده‌ام، اگرچه به نظر می‌رسد که مورد من از نوع کوانتومی است. مانند هر بیماری، گسترش بیماری مهم است. بنابراین در اینجا مجموعه ای از خواندنی ها در مورد مسئله ایزورموفیسم گراف ارائه شده است.
یکی از جنبه‌های جالب مسئله ایزومورفیسم گراف این است که کلاس‌هایی از نمودارها وجود دارند که الگوریتم‌های زمانی چند جمله‌ای کارآمدی برای تعیین هم‌شکل گراف‌ها در این کلاس‌ها وجود دارند. از آنجایی که می‌توان خیلی سریع سر خود را در برابر مشکل شکست داد، فکر می‌کنم خوب است که با یک مورد ساده شروع کنیم: هم‌شکل درختی. الگوریتم کارآمد برای این معمولا به آهو، هاپکرافت و اولمن (1974) نسبت داده می شود، اما من واقعا دوست دارم

• «الگوریتم‌های ایزومورفیسم درختی: سرعت در مقابل وضوح» توسط داگلاس ام. کمپبل و دیوید رادفورد ، مجله ریاضیات ، جلد. 64، شماره 4 (مهر، 1991)، صفحات 252-261

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

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

• «گواهینامه‌هایی برای نمودارها با مقادیر ویژه مشخص» توسط F. Thomson Leighton و Gary l. میلر، منتشر نشده، 1979 

مکان دیگری برای یادگیری در مورد این، بدون تمام علائم لک، در سایت دوره ییل دان اسپیلمن است:

• نظریه گراف طیفی، دن اسپیلمن، پاییز 2009 ( وب سایت دوره ، یادداشت هایی در مورد ایزومورفیسم گراف آزاد چندگانه)

در اینجا مکان خوبی برای ذکر حالت کلی برای تعدد محدود است

• "ایزومورفیسم نمودارها با کثرت مقدار ویژه محدود" توسط لازلو بابای، دی. یو. گریگوریف و دیوید ام مونت، STOC 1982 

منبع

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