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

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

دو گراف یکریخت اند اگر و فقط اگر تابعی یک به یک و پوشا به صورت ${\displaystyle f\colon V(G)\to V(H)\,\!}$ بین مجموعه رئوس دو گراف G و H وجود داشته باشد به طوری که ${\displaystyle uv\in E(G)}$ ، اگر و فقط اگر ${\displaystyle f(u)f(v)\in E(H)}$ .در این صورت دو گراف ${\displaystyle G}$ و ${\displaystyle H}$ را یکریخت گویند و می‌نویسند: ${\displaystyle 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

برای تعیین یکریخی دو گراف باید به چند مورد توجه شود:

1. تعداد رئوس
2. تعداد یال ها
3. درجهٔ هر یک از رئوس
4. همسایگی هر راس

برای مثال در شکل نشان داده شده این دو گراف یک ریخت‌اند.

بعد از مشاهده تعداد یال‌ها، راس‌ها، درجهٔ هر راس و نظیر کردن دو گراف به یکدیگر، می‌گوییم این دو گراف شرایط هم ریختی را دارند. (شرط لازم) اکنون باید هر راس گراف به دیگری نظیر شود. برای مثال در گراف رو برو: راس u1 دارای درجهٔ ۳ است، با دو راس درجهٔ ۲ (یعنی u5 و u4) و با یک راس درجهٔ ۳ (یعنی u3) همسایه است. نظیر این راس در گراف H می‌تواند راس v1 باشد چون این راس دقیقاً همهٔ خصوصیات راس u1 را دارد. همین مسیر را ادامه می‌دهیم. اگر در پایان کار مشاهده شد که همهٔ راس‌ها در دو گراف دو به دو نظیر اند می‌گوییم این دو گراف یک ریخت‌اند. (شرط کافی)

1. نظریه گراف
2. گراف (ریاضی)

1. Discrete Mathematics and Its Applications by Kenneth H Rosen Seventh Edition
2. کتاب ریاضیات گسسته و کاربردهای آن نوشته، کنت اچ. روزن ترجمه: حسین ابراهیم‌زاده قلزم – بهجت نصری خرمایی – قاسم جانیپور شهرود کلایی – زینب قربانی لاکتراشانی
3. ریچارد جانسون با. ساختمان‌های گسسته. ترجمهٔ حسین ابراهیم‌زاده قلزم. ویرایش پنجم. چاپ اول. سیمای دانش، ۱۳۸۰.