يرجى إضافة وصلات داخلية للمقالات المتعلّقة بموضوع المقالة.
يفتقر محتوى هذه المقالة إلى مصادر موثوقة.

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

من أرابيكا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث

تشاكل مخططين

معطيات : مخططين G=(S,A) وG=(S,A) المطلوب : المخططين G وG هل هما متشابهان ؟ أو بمعنى آخر, هل توجد دالة عكسية f:SS بحيث (u,v)S2,(u,v)A(f(u),f(v))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 ؟ أي بالمعنى الرياضي:

  • VV
  • EE(V×V)

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