تساوي شكل المخططات
تشاكل مخططين
معطيات : مخططين و المطلوب : المخططين و هل هما متشابهان ؟ أو بمعنى آخر, هل توجد دالة عكسية بحيث
هذا وتعتبر مسألة تصنيف مسألة التساوي الخاصة بالمخططات من المسائل غير المحلولة في الوقت الراهن، فالمسألة من صنف NP، لكن هل هي P أو NP_complet؟.
مثال
المخططان أدناه متشاكلان، رغم الاختلاف الكبير في طريقة رسمهما، والسبب هو وجود العلاقة الموضحة على الجانب الأيسر.
مخطط G | مخطط H | تشاكل بين G و H |
---|---|---|
|
تمديد المسألة
معطيات : مخططين و المطلوب : المخطط هل هو ضمن المخطط ؟ أي بالمعنى الرياضي:
و تعتبر المسألة أصعب بكثير من المسألة الأولى وهي تصنف ضمن NP_complet.
- بوابة رياضيات
- بوابة علم الحاسوب
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.