تساوي شكل المخططات

تشاكل مخططين

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