En la investigación de satisfacción de restricciones en inteligencia artificial e investigación de operaciones , se utilizan gráficos e hipergráficos de restricciones para representar las relaciones entre restricciones en un problema de satisfacción de restricciones . Un gráfico de restricciones es un caso especial de gráfico de factores , que permite la existencia de variables libres.
El hipergrafo de restricciones de un problema de satisfacción de restricciones es un hipergrafo en el que los vértices corresponden a las variables y los hiperbordes corresponden a las restricciones. Un conjunto de vértices forma un hiperborde si las variables correspondientes son las que ocurren en alguna restricción. [1]
Una forma sencilla de representar el hipergráfico de restricciones es utilizar un gráfico clásico con las siguientes propiedades:
Las propiedades 1 y 2 definen un gráfico bipartito . El hipergrafo se recupera definiendo los vértices como los vértices variables y los hiperbordes como los conjuntos de vértices variables conectados a cada vértice de restricción.
El gráfico de restricciones primal o simplemente gráfico primal (también gráfico de Gaifman ) de un problema de satisfacción de restricciones es el gráfico cuyos nodos son las variables del problema y una arista une un par de variables si las dos variables ocurren juntas en una restricción. [1]
El gráfico de restricción primaria es de hecho el gráfico primario del hipergráfico de restricción.
El conjunto de variables involucradas en una restricción se llama alcance de la restricción . El gráfico de restricción dual es el gráfico en el que los vértices son todos los alcances de restricción involucrados en las restricciones del problema, y dos vértices están conectados por un borde si los alcances correspondientes tienen variables comunes. [1]