رسم بياني للقيود

في أبحاث إرضاء القيود في الذكاء الاصطناعي وبحوث العمليات ، تُستخدم رسوم بيانية للقيود ورسوم بيانية فائقة لتمثيل العلاقات بين القيود في مسألة إرضاء القيود . يُعد الرسم البياني للقيود حالة خاصة من الرسم البياني للعوامل ، والذي يسمح بوجود متغيرات حرة.

الرسم البياني الفائق للقيود في مسألة إرضاء القيود هو رسم بياني فائق تمثل فيه الرؤوس المتغيرات، وتمثل فيه الحواف الفائقة القيود. تشكل مجموعة من الرؤوس حافة فائقة إذا كانت المتغيرات المقابلة لها هي تلك التي تظهر في أحد القيود. ^{[ 1 ]}

تتمثل إحدى الطرق البسيطة لتمثيل الرسم البياني الفائق للقيود في استخدام رسم بياني كلاسيكي بالخصائص التالية:

1. تمثل الرؤوس إما متغيرات أو قيودًا،
2. لا يمكن للحافة أن تربط إلا رأسًا متغيرًا برأس مقيد، و
3. توجد حافة بين رأس متغير ورأس قيد إذا وفقط إذا كان المتغير المقابل موجودًا في القيد المقابل.

تحدد الخاصيتان 1 و 2 الرسم البياني ثنائي الأجزاء . يتم استعادة الرسم البياني الفائق من خلال تعريف الرؤوس على أنها رؤوس متغيرة والحواف الفائقة على أنها مجموعات من الرؤوس المتغيرة المتصلة بكل رأس قيد.

الرسم البياني الأولي للقيود أو ببساطة الرسم البياني الأولي (ويسمى أيضًا رسم غايفمان البياني ) لمسألة إرضاء القيود هو الرسم البياني الذي تمثل عقده متغيرات المسألة، ويربط ضلع زوجًا من المتغيرات إذا ظهر المتغيران معًا في قيد واحد. ^{[ 1 ]}

إن الرسم البياني الأولي للقيود هو في الواقع الرسم البياني الأولي للرسم البياني الفائق للقيود.

تُسمى مجموعة المتغيرات المُتضمنة في قيدٍ ما بنطاق القيد . الرسم البياني للقيد المزدوج هو الرسم البياني الذي تكون فيه جميع الرؤوس عبارة عن نطاقات قيود مُتضمنة في قيود المسألة، ويرتبط رأسان بحافة إذا كانت النطاقات المُقابلة لهما متغيرات مشتركة. ^{[ 1 ]}