Primal graph

From Wikipedia, the free encyclopedia

In graph theory, the primal graph of a hypergraph is a graph with the same vertices of the hypergraph, and an edge between any pair of vertices contained in the same hyperedge.

In constraint satisfaction, the primal graph or primal constraint 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. The primal graph of a constraint satisfaction problem can also be defined as the primal graph of the hypergraph made of the variables and the constraint scopes.