حساب کاربری
​
تغیر مسیر یافته از - یکریختی گراف
زمان تقریبی مطالعه: 2 دقیقه
لینک کوتاه

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

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

فهرست

  • ۱ تعریف
  • ۲ مثال
  • ۳ تعیین یکریختی (Isomorphism)
  • ۴ چگونه بفهمیم که دو گراف یکریخت اند؟
  • ۵ جستارهای وابسته
  • ۶ منابع

تعریف

دو گراف یکریخت اند اگر و فقط اگر تابعی یک به یک و پوشا به صورت f : V ( G ) → V ( H ) {\displaystyle f\colon V(G)\to V(H)\,\!}

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

تعیین یکریختی (Isomorphism)

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

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

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

چگونه بفهمیم که دو گراف یکریخت اند؟

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

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

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

منابع

  1. ↑ West,Douglas,Introduction to Graph Theory,2nd Ed,P 7
  1. Discrete Mathematics and Its Applications by Kenneth H Rosen Seventh Edition
  2. کتاب ریاضیات گسسته و کاربردهای آن نوشته، کنت اچ. روزن ترجمه: حسین ابراهیم‌زاده قلزم – بهجت نصری خرمایی – قاسم جانیپور شهرود کلایی – زینب قربانی لاکتراشانی
  3. ریچارد جانسون با. ساختمان‌های گسسته. ترجمهٔ حسین ابراهیم‌زاده قلزم. ویرایش پنجم. چاپ اول. سیمای دانش، ۱۳۸۰.
آخرین نظرات
کلیه حقوق این تارنما متعلق به فرا دانشنامه ویکی بین است.