In constraint satisfaction research in artificial intelligence and operations research, constraint graphs and hypergraphs are used to represent relations among constraints in a constraint satisfaction problem. A constraint graph is a special case of a factor graph, which allows for the existence of free variables.
YouTube Encyclopedic
-
1/3Views:33 86663 76343 644
-
How to draw constraints on a graph - Linear Programming (LP)
-
LPP using Graphical method [ Maximization with two constraints ] solved problem :-by kauserwise
-
LPP Graphical Method(Minimization & Maximization with 3 Constraints) :-by kauserwise
Transcription
Constraint hypergraph
The constraint hypergraph of a constraint satisfaction problem is a hypergraph in which the vertices correspond to the variables, and the hyperedges correspond to the constraints. A set of vertices forms a hyperedge if the corresponding variables are those occurring in some constraint.[1]
A simple way to represent the constraint hypergraph is by using a classical graph with the following properties:
- Vertices correspond either to variables or to constraints,
- an edge can only connect a variable-vertex to a constraint-vertex, and
- there is an edge between a variable-vertex and a constraint-vertex if and only if the corresponding variable occurs in the corresponding constraint.
Properties 1 and 2 define a bipartite graph. The hypergraph is recovered by defining the vertices as the variable-vertices and the hyperedges as the sets of variable-vertices connected to each constraint-vertex.
Primal constraint graph
The primal constraint graph or simply primal graph (also the Gaifman graph) of a constraint satisfaction problem is the graph 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.[1]
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 constraint scopes involved in the constraints of the problem, and two vertices are connected by an edge if the corresponding scopes have common variables.[1]
References
- ^ a b c Handbook of Constraint Programming, by Francesca Rossi, Peter Van Beek, Toby Walsh (2006) ISBN 0-444-52726-5, p. 211, 212
This page was last edited on 12 October 2023, at 14:10