Loading [MathJax]/jax/output/HTML-CSS/jax.js

فهرست مندرجات

یک ریختی

فرض کنید G و H دو گراف ساده و f تابعی از مجموعه رئوس G به مجموعه رئوس H. (f:V(G)V(H)) تابعی یک به یک و پوشا باشد. f را یک تابع یک ریختی (ایزومورف) گوییم هرگاه برای هر دو رأس u و v از G، اگر u و v مجاور باشند(یا نباشند) آن گاه f(u) و f(v) در H مجاور باشند.(یا نباشند)
حال دو گراف G و H را یک ریخت می گوییم هرگاه یک یک ریختی بین آن ها موجود باشد. در واقع دو گراف G و H یکریخت اند هرگاه نموداری در صفحه وجود داشته باشد که بدون در نظر گرفتن برچسب برای رئوس هم نمودار G باشد و هم نمودار H.

هم ریختی

عمل مقدماتی روی گراف ساده ی ۱، یعنی حذف یال ۲ و اضافه کردن یال ها و رأس جدید ۳ به صورت ۴ و ۵. حال هرگاه دو گراف با چند عمل مقدماتی از یکدیگر به دست بیایند، آن ها را هم ریخت می نامیم.

خود ریختی

یک خودریختی گراف G، یک، یک ریختی از G به خودش است. اگر گراف ساده باشد، جایگشتی از رئوس است که مجاورت را حفظ کند. به عبارت دیگر α خودریختی گراف است هرگاه α جایگشتی از رئوس بوده و اگر uvE(G) آن گاه : α(u)α(v)E(G)