همریختی گراف

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

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

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

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Graph homomorphism». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۹ اوت ۲۰۲۰.
• Hell, Pavol; Nešetřil, Jaroslav (2004), Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications, vol. 28, Oxford University Press, ISBN 0-19-852817-5
• Hell, Pavol; Nešetřil, Jaroslav (2008), "Colouring, constraint satisfaction, and complexity" (PDF), Computer Science Review, 2 (3): 143–163, doi:10.1016/j.cosrev.2008.10.003, archived from the original (PDF) on 2017-07-06, retrieved 2017-04-09