В исследовании удовлетворения ограничений в области искусственного интеллекта и исследования операций графы ограничений и гиперграфы используются для представления отношений между ограничениями в задаче удовлетворения ограничений . Граф ограничений является частным случаем факторного графа , который допускает существование свободных переменных.
Гиперграф ограничений задачи удовлетворения ограничений — это гиперграф , в котором вершины соответствуют переменным, а гиперребра соответствуют ограничениям. Набор вершин образует гиперребро, если соответствующие переменные являются теми, которые встречаются в некотором ограничении. [1]
Простым способом представления гиперграфа ограничений является использование классического графа со следующими свойствами:
Свойства 1 и 2 определяют двудольный граф . Гиперграф восстанавливается путем определения вершин как переменных вершин и гиперребер как наборов переменных вершин, соединенных с каждой вершиной ограничения.
Граф первичных ограничений или просто первичный граф (также граф Гейфмана ) задачи удовлетворения ограничений — это граф , узлы которого являются переменными задачи, а ребро соединяет пару переменных, если две переменные встречаются вместе в ограничении. [1]
Первичный граф ограничений на самом деле является первичным графом гиперграфа ограничений.
Набор переменных, участвующих в ограничении, называется областью действия ограничений . Граф двойственных ограничений — это граф, в котором вершинами являются все области действия ограничений, участвующие в ограничениях задачи, и две вершины соединены ребром, если соответствующие области действия имеют общие переменные. [1]