تساوي مخططين
معطيات : ظ…ط®ط·ط·ظٹظ† G = (S,A) و G’ = (S’,A’) المطلوب : المخططين G و G’ هل هما متشابهان ؟ أو بمعنى آخر, هل توجد دالة عكسية بحيث
هذا و تعتبر مسألة تصنيف مسألة التساوي الخاصة بالمخططات من المسائل غير المحلولة في الوقت الراهن، فالمسألة من صنف NP، لكن هل هي P أو NP_complet؟.
المخططان أدناه متساويان، رغم الاختلاف الكبير في طريقة رسمهما، و السبب هو وجود العلاقة الموضحة على الجانب الأيسر.
Graph G Graph H An isomorphism
between G and 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 ؟ أي بالمعنى الرياضي:
و تعتبر المسألة أصعب بكثير من المسألة الأولى و هي تصنف ضمن NP_complet.
