الفرق بين المراجعتين لصفحة: «مشكلة المخطط الكامل ضمن مخطط»

من موسوعة العلوم العربية
اذهب إلى التنقل اذهب إلى البحث
ط (١ مراجعة: الصفحات في تصنيف رياضيات)
 
(تنظيف)
 
سطر 20: سطر 20:
[[تصنيف:رياضيات]]
[[تصنيف:رياضيات]]
[[تصنيف:نظرية المخططات]]
[[تصنيف:نظرية المخططات]]
[[de:Knotenüberdeckungen, Cliquen und stabile Mengen]]
[[en:Clique problem]]
[[es:Problema de la clique]]
[[he:גרף מלא]]
[[ja:最大クリーク問題]]
[[ko:클릭 문제]]
[[pl:Problem kliki]]
[[sr:Проблем клике]]
[[th:ปัญหากลุ่มพรรคพวก]]

المراجعة الحالية بتاريخ 13:21، 23 أغسطس 2012

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

تقديم المشكل

مخطط به زمرة

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

مبرهنة

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

البرهنة

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

مثال:

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