Constraint graph
कृत्रिम बुद्धिमत्ता और संचालन अनुसंधान में बाधा संतुष्टि अनुसंधान में, बाधा संतुष्टि समस्या में बाधाओं के बीच संबंधों का प्रतिनिधित्व करने के लिए बाधा ग्राफ और हाइपरग्राफ का उपयोग किया जाता है। एक बाधा ग्राफ एक कारक ग्राफ का एक विशेष मामला है, जो मुक्त चर के अस्तित्व की अनुमति देता है। एक बाधा संतुष्टि समस्या का बाधा हाइपरग्राफ एक हाइपरग्राफ है जिसमें शीर्ष चर के अनुरूप होते हैं, और हाइपरएज बाधाओं के अनुरूप होते हैं। शीर्षों का एक समूह एक हाइपरएज बनाता है यदि संबंधित चर कुछ बाधाओं में होते हैं। बाधा हाइपरग्राफ का प्रतिनिधित्व करने का एक सरल तरीका निम्नलिखित गुणों के साथ एक शास्त्रीय ग्राफ का उपयोग करना हैः वर्टीस या तो चर या बाधाओं के अनुरूप होते हैं, एक किनारा केवल एक चर-वर्टेक्स को एक बाधा-वर्टेक्स से जोड़ सकता है, और एक चर-वर्टेक्स और एक बाधा-वर्टेक्स के बीच एक किनारा होता है यदि और केवल तभी जब संबंधित चर संबंधित बाधा में होता है। गुण 1 और 2 एक द्विदलीय ग्राफ को परिभाषित करते हैं। हाइपरग्राफ को शीर्षों को चर-शीर्षों के रूप में परिभाषित करके और हाइपरएज को प्रत्येक बाधा-शीर्ष से जुड़े चर-शीर्षों के सेट के रूप में पुनर्प्राप्त किया जाता है। प्राइमल कन्स्ट्रेन्ट ग्राफ एक कन्स्ट्रेन्ट संतुष्टि समस्या का प्राइमल कन्स्ट्रेन्ट ग्राफ या केवल प्राइमल ग्राफ (गैफमैन ग्राफ भी) वह ग्राफ है जिसके नोड्स समस्या के चर हैं और एक किनारा चर की एक जोड़ी में शामिल हो जाता है यदि दोनों चर एक साथ एक बाधा में होते हैं। प्राइमल कन्स्ट्रेन्ट ग्राफ वास्तव में कन्स्ट्रेन्ट हाइपरग्राफ का प्राइमल ग्राफ है। दोहरी बाधा ग्राफ एक बाधा में शामिल चरों के समूह को बाधा दायरा कहा जाता है। दोहरा बाधा ग्राफ वह ग्राफ है जिसमें शीर्ष समस्या की बाधाओं में शामिल सभी बाधा क्षेत्र हैं, और दो शीर्ष एक किनारे से जुड़े हुए हैं यदि संबंधित दायरे में सामान्य चर हैं। संदर्भ बाधा प्रोग्रामिंग अनुप्रयोग-विशिष्ट ग्राफ