مشكلة المخطط الكامل ضمن مخطط
المخطط الكامل هو مخطط كل رأسين فيه مرتبطان.[1] ورتبة المخطط الكامل هو عدد رؤوسه.
هذه المقالة ليس بها أي وصلات لمقالاتٍ أخرى للمساعدة في ترابط مقالات ويكيبيديا. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (أبريل 2019)
| مسألة NP كاملة |
|---|
| زمرة كبرى |
| مسار هاملتونياني |
| عدل |
تقديم المشكل
مخطط به زمرة
الهدف هو إيجاد المخطط الكامل ذو أكبر رتبة, والموجود ضمن مخطط معلوم.
البرهنة
تتم من خلال تحديد اختصار حدودي من مشكل الاكتفاء من الرتبة 3 نحو مشكل المخطط الكامل:
مثال:
انطلاقا من هذه الصيغة تحدد مخططا غير موجه يضم 12 قمة كل قمة تمثل متغيرا واحدا. أما الارتباطات فهي كل قمتين يتم ربطهما برابط, ما عدا القمم التي تمثل متغيرات من نفس القوس, وكذلك لا نربط بين قمة تمثل متغيرا مع عكسه.(انظر الصورة)
مراجع
- DIMACS challenge graphs for the clique problem, accessed 2009-12-17. نسخة محفوظة 1 أبريل 2018 على موقع واي باك مشين.
بوابة رياضيات
بوابة علم الحاسوب
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.