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

تشاكل مخططين

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

هذا وتعتبر مسألة تصنيف مسألة التساوي الخاصة بالمخططات من المسائل غير المحلولة في الوقت الراهن، فالمسألة من صنف 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^{\prime }=(S^{\prime },A^{\prime })$ المطلوب : المخطط $G^{\prime }$ هل هو ضمن المخطط $G$ ؟ أي بالمعنى الرياضي:

• $V\subseteq V^{\prime }$
• $E\subseteq E^{\prime }\cap (V\times V)$

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