تماكل بيانين

معطيات : بيانين ${\displaystyle G=(S,A)}$ و${\displaystyle G'=(S',A')}$ المطلوب : البيانين ${\displaystyle G}$ و${\displaystyle G'}$ هل هما متشابهان ؟ أو بمعنى آخر, هل توجد دالة عكسية ${\displaystyle f:S\rightarrow S'}$ بحيث ${\displaystyle \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
		${\displaystyle f(a)=1}$ ${\displaystyle f(b)=6}$ ${\displaystyle f(c)=8}$ ${\displaystyle f(d)=3}$ ${\displaystyle f(g)=5}$ ${\displaystyle f(h)=2}$ ${\displaystyle f(i)=4}$ ${\displaystyle f(j)=7}$

تمديد المسألة

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

• ${\displaystyle V\subseteq V'}$
• ${\displaystyle E\subseteq E'\cap (V\times V)}$

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

المراجع