Constraint graph
مصنوعی ذہانت اور کارروائیوں کی تحقیق میں رکاوٹ اطمینان کی تحقیق میں، رکاوٹ اطمینان کے مسئلے میں رکاوٹوں کے درمیان تعلقات کی نمائندگی کے لیے رکاوٹ گراف اور ہائپر گراف کا استعمال کیا جاتا ہے۔ رکاوٹ گراف عنصر گراف کا ایک خاص معاملہ ہے، جو آزاد متغیرات کے وجود کی اجازت دیتا ہے۔ رکاوٹ ہائپر گراف رکاوٹ اطمینان کے مسئلے کا رکاوٹ ہائپر گراف ایک ہائپر گراف ہے جس میں عمودی متغیرات سے مطابقت رکھتے ہیں، اور ہائپر ایجز رکاوٹوں سے مطابقت رکھتے ہیں۔ عمودی حصوں کا ایک مجموعہ ایک ہائپر ایج بناتا ہے اگر متعلقہ متغیرات وہ ہیں جو کسی رکاوٹ میں پائے جاتے ہیں۔ رکاوٹ ہائپر گراف کی نمائندگی کرنے کا ایک آسان طریقہ مندرجہ ذیل خصوصیات کے ساتھ کلاسیکی گراف کا استعمال کرنا ہے: عمودی یا تو متغیرات یا رکاوٹوں سے مطابقت رکھتے ہیں، ایک کنارے صرف ایک متغیر-ورٹیکس کو رکاوٹ-ورٹیکس سے جوڑ سکتا ہے، اور متغیر-ورٹیکس اور رکاوٹ-ورٹیکس کے درمیان ایک کنارے ہوتا ہے اگر اور صرف اس صورت میں جب متعلقہ متغیر اسی رکاوٹ میں واقع ہوتا ہے۔ خصوصیات 1 اور 2 دو طرفہ گراف کی وضاحت کرتے ہیں۔ ہائپر گراف کو عمودی کو متغیر عمودی کے طور پر اور ہائپر ایجز کو ہر رکاوٹ ورٹیکس سے منسلک متغیر عمودی کے سیٹ کے طور پر بیان کرکے بازیافت کیا جاتا ہے۔ ابتدائی رکاوٹ گراف کسی رکاوٹ کے اطمینان کے مسئلے کا ابتدائی رکاوٹ گراف یا محض ابتدائی گراف (گیفمین گراف بھی) وہ گراف ہے جس کے نوڈس مسئلے کے متغیر ہوتے ہیں اور اگر دونوں متغیرات ایک ساتھ پائے جاتے ہیں تو ایک کنارے متغیرات کے جوڑے میں شامل ہو جاتا ہے۔ ابتدائی رکاوٹ گراف درحقیقت رکاوٹ ہائپر گراف کا بنیادی گراف ہے۔ دوہری رکاوٹ گراف کسی رکاوٹ میں شامل متغیرات کے سیٹ کو رکاوٹ کا دائرہ کہا جاتا ہے۔ دوہری رکاوٹ گراف وہ گراف ہے جس میں عمودی مسائل کی رکاوٹوں میں شامل تمام رکاوٹ کے دائرے ہوتے ہیں، اور اگر متعلقہ دائرے میں مشترک متغیرات ہوں تو دو عمودی ایک کنارے سے جڑے ہوتے ہیں۔ حوالہ جات رکاوٹ پروگرامنگ ایپلی کیشن مخصوص گراف