همریختی گراف

همریختی^[۱] گراف (به انگلیسی: Graph homomorphism) در زمینه نظریه گراف در ریاضیات، نوعی نگاشت مرتبط با ساختار در بین دو گراف است. اگر دقیق‌تر بگوییم، همریختی نوعی تابع بین مجموعه راس‌های دو گراف است، که در آن راس‌های مجاور در یک گراف به راس‌های مجاور در گراف دیگر تناظر می‌یابد.

یک همریختی از گل اسنارک J₅ به گراف چرخه دار C_5.
این یک انقباض به سمت زیرگراف روی پنج راس درونی است. بنابراین J₅ در واقع هم‌ارز با C₅ مرکزی است.

همریختی مفاهیم متنوع رنگ‌آمیزی گراف را تعمیم می‌دهد، و این مفهوم، امکان بیان کلاس مهمی از مسائل ارضای محدودیت را می‌دهد، (مثل مسائل زمان‌بندی یا انتساب فرکانس).^[۲] این یک واقعیت است که یکریختی‌ها می‌توانند ترکیب شوند و منجر به ساختارهای جبری قوی‌تری شوند:مثل پیش‌ترتیب دربارهٔ گراف‌ها، مشبکه توزیع پذیر، و یک رسته (یکی برای گراف‌های بدون جهت و یکی برای گراف‌های جهت دار).^[۳]

پیچیدگی محاسباتی برای یافتن همریختی بین گراف‌های داده شده می‌تواند بسیار پرهزینه و بازدارنده باشد، ولی در مورد حالات خاصی که در زمان چندجمله‌ای قابل حل است، چیزهای زیادی می‌دانیم. یافتن خط مرزی بین حالات قابل حل و غیرقابل حل، یک زمینه پژوهشی فعال و پرتوجه می‌باشد.^[۴]