الرئيسية موسوعتي بحث

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

تشاكل مخططين

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

تصنيفات الصفحة: رياضيات متقطعة | نظرية المخططات