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

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

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

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

پیچیدگی محاسباتی

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

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

الگوریتم‌ها، نرم‌افزار و برنامه‌ها

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

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

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