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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

تعریف[ویرایش]

دو گراف یکریخت اند اگر و فقط اگر تابعی یک به یک و پوشا به صورت بین مجموعه رئوس دو گراف G و H وجود داشته باشد به طوری که ، اگر و فقط اگر .در این صورت دو گراف و را یکریخت گویند و می‌نویسند: .[۱]

مثال[ویرایش]

دو گراف زیر با این که ظاهر متفاوتی دارند اما با هم یکریختند.

Graph G Graph H An isomorphism
between G and H
Graph isomorphism a.svg Graph isomorphism b.svg ƒ(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. ریچارد جانسون با. ساختمان‌های گسسته. ترجمهٔ حسین ابراهیم‌زاده قلزم. ویرایش پنجم. چاپ اول. سیمای دانش، ۱۳۸۰.