linguistic:voice_change, information:filtering
Formal view

Graphs and directed graphs can be viewed as a special case of the far more general notion called relational structures (defined as a set with a tuple of relations on it). Directed graphs are structures with a single binary relation (adjacency) on the domain (the vertex set). Under this view, homomorphisms of such structures are exactly graph homomorphisms.In general, the question of finding a homomorphism from one relational structure to another is a constraint satisfaction problem (CSP).The case of graphs gives a concrete first step that helps to understand more complicated CSPs.Many algorithmic methods for finding graph homomorphisms, like backtracking, constraint propagation and local search, apply to all CSPs.

For graphs G and H, the question of whether G has a homomorphism to H corresponds to a CSP instance with only one kind of constraint, as follows. The variables are the vertices of G and the domain for each variable is the vertex set of H. An evaluation is a function that assigns to each variable an element of the domain, so a function f from V (G) to V (H). Each edge or arc (u, v) of G then corresponds to the constraint ((u, v), E(H)). This is a constraint expressing that the evaluation should map the arc (u, v) to a pair (f (u), f (v)) that is in the relation E (H), that is, to an arc of H. A solution to the CSP is an evaluation that respects all constraints, so it is exactly a homomorphism from G to H.