Constraint graph
Encyclopedia
In constraint satisfaction
research of artificial intelligence
and operations research
, constraint graphs and hypergraphs are used to represent relations among constraints in a constraint satisfaction problem
.
in which hypervertices correspond to the variables and the hyperedges correspond to the constraints. Two hypervertices are in the same hyperedge if the two variables occur in the same constraint.
whose nodes are the variables of the problem and an edge joins a pair of variables if the two variables occur together in a constraint.
The primal constraint graph is in fact the primal graph of the constraint hypergraph.
The dual constraint graph is the graph in which the vertices are all possible constraint scopes involved in the constraints of the problem and two vertices are connected by an edge if the corresponding scopes have common variables.
Constraint satisfaction
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.The techniques used in...
research of artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
and operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
, constraint graphs and hypergraphs are used to represent relations among constraints in a constraint satisfaction problem
Constraint satisfaction problem
Constraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint...
.
Constraint hypergraph
The constraint hypergraph of a constraint satisfaction problem is a hypergraphHypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
in which hypervertices correspond to the variables and the hyperedges correspond to the constraints. Two hypervertices are in the same hyperedge if the two variables occur in the same constraint.
Primal constraint graph
The primal constraint graph or simply primal graph (also the Gaifman graph) of a constraint satisfaction problem is the graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
whose nodes are the variables of the problem and an edge joins a pair of variables if the two variables occur together in a constraint.
The primal constraint graph is in fact the primal graph of the constraint hypergraph.
Dual constraint graph
The set of variables involved in a constraint is called the constraint scope.The dual constraint graph is the graph in which the vertices are all possible constraint scopes involved in the constraints of the problem and two vertices are connected by an edge if the corresponding scopes have common variables.