تشاكل المخططات

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

تشاكل مخططين[عدل]

معطيات : مخططين G=(S,A) وG'=(S',A') المطلوب : المخططين G وG' هل هما متشابهان ؟ أو بمعنى آخر, هل توجد دالة عكسية f : S \rightarrow S' بحيث \forall (u,v) \in S^2, (u,v) \in A \Leftrightarrow (f(u),f(v)) \in A'

هذا وتعتبر مسألة تصنيف مسألة التساوي الخاصة بالمخططات من المسائل غير المحلولة في الوقت الراهن، فالمسألة من صنف NP، لكن هل هي P أو NP_complet؟.

مثال[عدل]

المخططان أدناه متشاكلان، رغم الاختلاف الكبير في طريقة رسمهما، والسبب هو وجود العلاقة الموضحة على الجانب الأيسر.

مخطط G مخطط H تشاكل
بين G و H
Graph isomorphism a.svg Graph isomorphism b.svg  f(a) = 1

 f(b) = 6

 f(c) = 8

 f(d) = 3

 f(g) = 5

 f(h) = 2

 f(i) = 4

 f(j) = 7

تمديد المسألة[عدل]

معطيات : مخططين G=(S,A) وG'=(S',A') المطلوب : المخطط G' هل هو ضمن المخطط G ؟ أي بالمعنى الرياضي:

  •  V \subseteq V'
  •  E \subseteq E' \cap (V \times V)

و تعتبر المسألة أصعب بكثير من المسألة الأولى وهي تصنف ضمن NP_complet.