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

تشاكل مخططين

معطيات : مخططين 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
		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.