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

(تم التحويل من زمرة كبرى)
brute force algorithm finds a 4-clique in this 7-vertex graph (the complement of the 7-vertex path graph) by systematically checking all C(7,4)=35 4-vertex subgraphs for completeness.

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

تقديم المشكل

مخطط به زمرة
مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل


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


المبرهنة

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

البرهان

Sattoclique.png

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

مثال:

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