English  

كتب complete schema problem within schema

اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.

عرض المزيد

مشكلة المخطط الكامل ضمن مخطط (معلومة)


هذه المقالة ليس بها أي وصلات لمقالاتٍ أخرى للمساعدة في ترابط مقالات ويكيبيديا. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (أبريل 2019)

المخطط الكامل هو مخطط كل رأسين فيه مرتبطان. ورتبة المخطط الكامل هو عدد رؤوسه.

تقديم المشكل

الهدف هو إيجاد المخطط الكامل ذو أكبر رتبة, والموجود ضمن مخطط معلوم.

مبرهنة

تحديد المخطط الكامل ضمن مخطط, مشكل كامل.

البرهنة

تتم من خلال تحديد اختصار حدودي من مشكل الاكتفاء من الرتبة 3 نحو مشكل المخطط الكامل:

مثال:

انطلاقا من هذه الصيغة تحدد مخططا غير موجه يضم 12 قمة كل قمة تمثل متغيرا واحدا. أما الارتباطات فهي كل قمتين يتم ربطهما برابط, ما عدا القمم التي تمثل متغيرات من نفس القوس, وكذلك لا نربط بين قمة تمثل متغيرا مع عكسه.(انظر الصورة)

المصدر: wikipedia.org