تم النشر اليوم 2024/06/06 | مشكلة المخطط الكامل ضمن مخطط

مبرهنة

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

تقديم المشكل

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

البرهنة

تتم من خلال تحديد اختصار حدودي من مشكل الاكتفاء من الرتبة 3 نحو مشكل المخطط الكامل: مثال:
(
a
∨
¬
b
∨
c
)
∧
(
a
∨
b
∨
¬
d
)
∧
(
a
∨
c
∨
e
)
∧
(
b
∨
d
∨
¬
e
)
{displaystyle (alor lnot blor c)wedge (alor blor lnot d)wedge (alor clor e)wedge (blor dlor lnot e)}
انطلاقا من هذه الصيغة تحدد مخططا غير موجه يضم 12 قمة كل قمة تمثل متغيرا واحدا. أما الارتباطات فهي كل قمتين يتم ربطهما برابط, ما عدا القمم التي تمثل متغيرات من نفس القوس, وكذلك لا نربط بين قمة تمثل متغيرا مع عكسه.(انظر الصورة)

شرح مبسط

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