افتح القائمة الرئيسية
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016)

تشاكل مخططينعدل

معطيات : مخططين   و  المطلوب : المخططين   و  هل هما متشابهان ؟ أو بمعنى آخر, هل توجد دالة عكسية   بحيث  

هذا وتعتبر مسألة تصنيف مسألة التساوي الخاصة بالمخططات من المسائل غير المحلولة في الوقت الراهن، فالمسألة من صنف NP، لكن هل هي P أو NP_complet؟.

مثالعدل

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

مخطط G مخطط H تشاكل
بين G و H
     

 

 

 

 

 

 

 

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

معطيات : مخططين   و  المطلوب : المخطط   هل هو ضمن المخطط   ؟ أي بالمعنى الرياضي:

  •  
  •  

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

 
هذه بذرة مقالة عن الرياضيات بحاجة للتوسيع. شارك في تحريرها.