المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:گراف:یک‌ریختی٬ هم‌ریختی و خودریختی

یک ریختی

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

هم ریختی

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

خود ریختی

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


ابزار صفحه