یک ریختی

گراف های یکسان

گراف G و H را در نظر بگیرید. اگر V(G) = V(H) و E(G) = E(H) باشد گوییم گراف های G و H یکسان هستند.

یک ریختی

گراف G و H را در نظر بگیرید. تابع یک به یک و پوشا f(u) را تعریف کنیم راس تناظر داده شده در گراف H از راس u در گراف G و با این شرط که f(u) و f(v) با هم برابرند تنها در صورتی که u برابر با v باشد. اگر بتوان یک تابع f بین راس های G و H ایجاد کرد که با قراردادن f هر راس u در گراف G جای خود راس u این دو گراف یکسان شود، گوییم این دو گراف یک ریخت هستند. به عبارت دیگه یال uv در G وجود دارد اگر و تنها اگر یال f(u)f(v) هم در H وجود داشته باشد؛ در این صورت دو گراف یک ریخت هستند.

خود ریختی

تعریف ساده خود ریختی،یک ریختی گراف به خودش است. یعنی با جایگشت دادن راس های گراف مجموعه یال ها تغییر نکند.