مشكلة المخطط الكامل ضمن مخطط
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 كاملة |
|---|
|
|
| زمرة كبرى |
| مسار هاملتونياني |
| عدل |
الهدف هوإيجاد المخطط الكامل ذوأكبر رتبة, والموجود ضمن مخطط معلوم.
المبرهنة
تحديد المخطط الكامل ضمن مخطط، مأزق كامل.
البرهان
تتم من خلال تحديد اختصار حدودي من مأزق الاكتفاء من الرتبة ثلاثة نحومأزق المخطط الكامل:
مثال:
انطلاقا من هذه الصيغة تحدد مخططا غير موجه يضم 12 قمة جميع قمة تمثل متغيرا واحدا. أما الإرتباطات فهي جميع قمتين يتم ربطهما برابط، ما عدا القمم التي تمثل متغيرات من نفس القوس، وكذلك لا نربط بين قمة تمثل متغيرا مع عكسه. (انظر الصورة)
