همریختی[ ۱] گراف ( به انگلیسی: Graph homomorphism ) در زمینه نظریه گراف در ریاضیات، نوعی نگاشت مرتبط با ساختار در بین دو گراف است. اگر دقیق تر بگوییم، همریختی نوعی تابع بین مجموعه راس های دو گراف است، که در آن راس های مجاور در یک گراف به راس های مجاور در گراف دیگر تناظر می یابد.
همریختی مفاهیم متنوع رنگ آمیزی گراف را تعمیم می دهد، و این مفهوم، امکان بیان کلاس مهمی از مسائل ارضای محدودیت را می دهد، ( مثل مسائل زمان بندی یا انتساب فرکانس ) . [ ۲] این یک واقعیت است که یکریختی ها می توانند ترکیب شوند و منجر به ساختارهای جبری قوی تری شوند:مثل پیش ترتیب دربارهٔ گراف ها، مشبکه توزیع پذیر، و یک رسته ( یکی برای گراف های بدون جهت و یکی برای گراف های جهت دار ) . [ ۳]
پیچیدگی محاسباتی برای یافتن همریختی بین گراف های داده شده می تواند بسیار پرهزینه و بازدارنده باشد، ولی در مورد حالات خاصی که در زمان چندجمله ای قابل حل است، چیزهای زیادی می دانیم. یافتن خط مرزی بین حالات قابل حل و غیرقابل حل، یک زمینه پژوهشی فعال و پرتوجه می باشد. [ ۴]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفهمریختی مفاهیم متنوع رنگ آمیزی گراف را تعمیم می دهد، و این مفهوم، امکان بیان کلاس مهمی از مسائل ارضای محدودیت را می دهد، ( مثل مسائل زمان بندی یا انتساب فرکانس ) . [ ۲] این یک واقعیت است که یکریختی ها می توانند ترکیب شوند و منجر به ساختارهای جبری قوی تری شوند:مثل پیش ترتیب دربارهٔ گراف ها، مشبکه توزیع پذیر، و یک رسته ( یکی برای گراف های بدون جهت و یکی برای گراف های جهت دار ) . [ ۳]
پیچیدگی محاسباتی برای یافتن همریختی بین گراف های داده شده می تواند بسیار پرهزینه و بازدارنده باشد، ولی در مورد حالات خاصی که در زمان چندجمله ای قابل حل است، چیزهای زیادی می دانیم. یافتن خط مرزی بین حالات قابل حل و غیرقابل حل، یک زمینه پژوهشی فعال و پرتوجه می باشد. [ ۴]
wiki: همریختی گراف