يرجى إضافة وصلات داخلية للمقالات المتعلّقة بموضوع المقالة.

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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

تقديم المشكل[عدل]

مخطط به زمرة

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

مبرهنة[عدل]

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

البرهنة[عدل]

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

مثال:

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

Sattoclique.png

مراجع[عدل]


Nuvola apps edu mathematics-ar.svg
هذه بذرة مقالة عن الرياضيات بحاجة للتوسيع. شارك في تحريرها.