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

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

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

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

دو گراف یکریخت اند اگر و فقط اگر تابعی یک به یک و پوشا به صورت  f \colon V(G) \to V(H) \,\! بین مجموعه رئوس دو گراف G و H وجود داشته باشد به طوری که uv \in E(G) ، اگر و فقط اگر f(u)f(v) \in E(H) .در این صورت دو گراف G و H را یکریخت گویند و می‌نویسند:  G \cong 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