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

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از یکریختی گراف)
پرش به: ناوبری، جستجو

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

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

دو گراف یکریخت اند اگر و فقط اگر تابعی یک به یک و پوشا به صورت بین مجموعه رئوس دو گراف 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

تعیین یکریختی[ویرایش]

تصور می‌شود مسألهٔ تعیین یکریختی گراف نه NP-Complete باشد و نه P. البته این موضوع تاکنون ثابت نشده است.[۲]

جستارهای وابسته[ویرایش]

نظریه گراف

منابع[ویرایش]

  1. West,Douglas,Introduction to Graph Theory,2nd Ed,P 7
  2. Isomorphic Graphs - from Wolfram MathWorld