یک‌ریختی گراف

دو گراف که تعداد یکسانی رأس دارند و این رأس‌ها نیز به صورت مشابهی به یکدیگر متصل گشته‌اند، یکریخت نامیده می‌شوند.

تعریف

دو گراف یکریخت اند اگر و فقط اگر تابعی یک به یک و پوشا به صورت $f \colon V(G) \to V(H) \,\!$ بین مجموعه رئوس دو گراف G و H وجود داشته باشد به طوری که $uv \in E(G)$ ، اگر و فقط اگر $f(u)f(v) \in E(H)$ .در این صورت دو گراف $G$ و $H$ را یکریخت گویند و می‌نویسند: $G \cong H$ .

مثال

دو گراف زیر با این که ظاهر متفاوتی دارند اما با هم یکریختند.

Graph G	Graph H	An isomorphism between G and H
		ƒ(a) = 1 ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7

تعیین یکریختی

تصور می‌شود مسألهٔ تعیین یکریختی گراف نه NP-Complete باشد و نه P. البته این موضوع تاکنون ثابت نشده است.

جستارهای وابسته

نظریه گراف