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

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

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

تقديم المشكل

ملف:6n-graf-clique.svg

مخطط به زمرة

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

مبرهنة

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

البرهنة

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

مثال: $(a\vee \mathrm{\neg }b\vee c)\wedge (a\vee b\vee \mathrm{\neg }d)\wedge (a\vee c\vee e)\wedge (b\vee d\vee \mathrm{\neg }e)$

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

ملف:Sattoclique.png

ملف:Nuvola apps edu mathematics-ar.svg

هذه بذرة مقالة عن الرياضيات تحتاج للنمو والتحسين، فساهم في إثرائها بالمشاركة في تحريرها.

ملف:Nuvola apps edu mathematics-ar.svg

بوابة رياضيات تصفح مقالات ويكيبيديا المهتمة بالرياضيات.

de:Knotenüberdeckungen, Cliquen und stabile Mengen Clique problem]] es:Problema de la clique he:גרף מלא ja:最大クリーク問題 ko:클릭 문제 pl:Problem kliki sr:Проблем клике th:ปัญหากลุ่มพรรคพวก