مشكلة المخطط الكامل ضمن مخطط

مسألة NP كاملة
قابلية الإرضاء 3سات NAE أو آي تي
تلوين مخطط تلوين مخطط بثلاثة ألوان تلوين مخطط مستو بثلاثة ألوان
زمرة كبرى
مسار هاملتونياني
عدل

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

تقديم المشكل

مخطط به زمرة

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

مبرهنة

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

البرهنة

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

مثال: $(a\lor \lnot b\lor c)\wedge (a\lor b\lor \lnot d)\wedge (a\lor c\lor e)\wedge (b\lor d\lor \lnot e)$

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