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

تشاكل مخططين

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

مثال

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

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

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

موسوعات ذات صلة :

• موسوعة رياضيات