عرض مصدر مشكلة المخطط الكامل ضمن مخطط

{{وصلات قليلة|تاريخ=أبريل 2022}}
{{مسألة NP كاملة}}

'''المخطط الكامل''' هو [[مضلع]] كل رأسين فيه مرتبطان.<ref>[ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/ DIMACS challenge graphs for the clique problem], accessed 2009-12-17. {{Webarchive|url=https://web.archive.org/web/20180401191007/http://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/ |date=1 أبريل 2018}}</ref> ورتبة المخطط الكامل هو عدد رؤوسه.

== تقديم المشكل ==
[[ملف:6n-graf-clique.svg|تصغير|مخطط به زمرة]]
الهدف هو إيجاد المخطط الكامل ذو أكبر رتبة, والموجود ضمن مخطط معلوم.
== مبرهنة ==
تحديد المخطط الكامل ضمن [[نظرية المخططات#تعاريف|مخطط]], [[نظرية التعقيد الحسابي|مشكل كامل]].

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

مثال:
<math>(a\lor \lnot b\lor c)\wedge(a\lor b\lor\lnot d)\wedge(a\lor c\lor e)\wedge(b\lor d\lor\lnot e)</math>

انطلاقا من هذه الصيغة تحدد مخططا غير موجه يضم 12 قمة كل قمة تمثل متغيرا واحدا. أما الارتباطات فهي كل قمتين يتم ربطهما برابط, ما عدا القمم التي تمثل متغيرات من نفس القوس, وكذلك لا نربط بين قمة تمثل متغيرا مع عكسه.(انظر الصورة) [[ملف:sattoclique.svg|تصغير]]
== مراجع ==
{{مراجع}}

{{شريط بوابات|رياضيات|علم الحاسوب}}

{{بذرة رياضيات}}

[[تصنيف:مسائل كثيرة حدود غير قطعية كاملة]]
[[تصنيف:معضلات حاسوبية في نظرية المخططات]]