خودریختی گراف

در زمینه ریاضیات نظریه گراف (ریاضی)، خود ریختی یک گراف،  حالتی تقارن است که در آن گراف به خود نگاشت دارد در حالی که اتصال بین راس-یال را حفظ می کند.

به طور عمومی، خود ریختی یک گراف G = (V, E) یک جایگشت از رئوس مجموعه V است به طوری که جفت رئوس (u, v) یک یال را تشکیل بدهند اگر و تنها اگر جفت رئوس  (σ(u), σ(v)) نیز یک یال را تشکیل دهند. و این یک ریختی گراف G به خودش است. خود ریختی می تواند به همین شکل برای گراف ها جهت دار و بدون جهت تعریف شود.

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

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

مسئله خودریختی گراف، یک مسئله برای آزمایش این است که آیا یک گراف دارای خود ریختی غیر معمول است یا خیر. این مسئله به کلاس پیچیدگی NP تعلق دارد. مشابه مسئله  یک ریختی مشخص نیست که آیا این مسئله الگوریتم زمان اجرای چند جمله ای دارد یا جز NP-complete است. یک الگوریتم زمان اجرای چند جمله ای برای حل مسئله خود ریختی گراف برای گراف های که درجات رئوس به یک مقدار ثابت محدود شده اند وجود دارد. مسئله خود ریختی گراف چند جمله ای زمان چند جمله ای است که قابل تقلیل به مسئله یک ریختی گراف است، اما کاهش معکوس ناشناخته است. در مقابل دشواری کار زمانی خود را نشان می دهد که خود ریختی به شیوه خاصی محدود شده باشد. برای مثال ، تعیین وجود یک خود ریختی بدون نقطه ثابت (خود ریختی که هیچ راسی را ثابت نمی کند) NP-complete است و مسئله شمارش چنین خود ریختی ♯P-complete است.

الگوریتم ها ، نرم افزار و برنامه ها 
در حالی که هیچ الگوریتم زمان چند جمله‌ای بدترین حالت برای مسئله عمومی خود ریختی گراف شناخته شده نیست، یافتن گروه خود ریختی (و چاپ مجموعه‌ ای از سازنده ضروری) برای بسیاری از گراف های بزرگ که در برنامه‌ ها ایجاد می‌ شوند، نسبتاً آسان است. چندین ابزار نرم افزار متن باز برای این کار در دسترس هستند، از جمله NAUTY،  BLISS  و SAUCY . SAUCY و BLISS به ویژه برای گراف های پراکنده کارآمد هستند، به عنوان مثال، SAUCY برخی از گراف ها را با میلیون ها راس در  چند ثانیه پردازش می کند. با این حال، BLISS و NAUTY همچنین می‌ توانند علامت گذاری متعارف را تولید کنند، در حالی که SAUCY در حال حاضر برای حل خود ریختی گراف بهینه شده است.

یکی از نظرات مهم این است که برای یک گراف با n راس ، گروه خود ریختی را نمی توان بیش از n-1 سازنده نشان داد. و بسته‌ های نرم‌ افزاری فوق تضمین شده‌ اند که این محدودیت را به‌ عنوان اثر جانبی الگوریتم‌ های آن‌ ها برآورده می‌ کنند ( مجموعه‌ های حداقلی از سازنده ها سخت‌ تر پیدا می‌ شوند و به ویژه در عمل مفید نیستند). همچنین به نظر می رسد که پشتیبانی کل (یعنی تعداد رئوس جابجا شده) همه سازنده ها با یک تابع خطی n محدود شده است که در تحلیل زمان اجرا این الگوریتم ها مهم است. با این حال، از مارس 2012، این امر برای یک واقعیت ثابت نشده است.

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