Grafo de restricciones

En la investigación sobre satisfacción de restricciones en inteligencia artificial e investigación operativa , se utilizan grafos e hipergrafos de restricciones para representar las relaciones entre las restricciones en un problema de satisfacción de restricciones . Un grafo de restricciones es un caso especial de un grafo factorial , 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 las hiperaristas a las restricciones. Un conjunto de vértices forma una hiperarista si las variables correspondientes son las que aparecen en alguna restricción. ^{[ 1 ]}

Una forma sencilla de representar el hipergrafo de restricciones es mediante el uso de un grafo clásico con las siguientes propiedades:

1. Los vértices corresponden a variables o a restricciones,
2. una arista solo puede conectar un vértice variable con un vértice de restricción, y
3. Existe una arista entre un vértice de variable y un vértice de restricción si y solo si la variable correspondiente aparece en la restricción correspondiente.

Las propiedades 1 y 2 definen un grafo bipartito . El hipergrafo se recupera definiendo los vértices como vértices variables y las hiperaristas como conjuntos de vértices variables conectados a cada vértice de restricción.

El grafo de restricciones primales o simplemente grafo primal (también conocido como grafo de Gaifman ) de un problema de satisfacción de restricciones es el grafo cuyos nodos son las variables del problema y una arista une un par de variables si estas aparecen juntas en una restricción. ^{[ 1 ]}

El grafo de restricciones primal es, de hecho, el grafo primal del hipergrafo de restricciones.

El conjunto de variables involucradas en una restricción se denomina ámbito de restricción . El grafo de restricción dual es el grafo en el que los vértices son todos los ámbitos de restricción involucrados en las restricciones del problema, y ​​dos vértices están conectados por una arista si los ámbitos correspondientes tienen variables comunes. ^{[ 1 ]}