Editing Graph homomorphism (section)

===Formal view===
Graphs and directed graphs can be viewed as a special case of the far more general notion called relational [[Structure (mathematical logic)|structure]]s (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).<ref name="HN-csp">{{harvnb|Hell|Nešetřil|2004|p=28}}, note ''relational structures'' are called ''relational systems'' there.</ref>{{sfn|Hell|Nešetřil|2008}} Under this view, [[Structure (mathematical logic)#Homomorphisms|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 (constraint satisfaction)|local search]], apply to all CSPs.{{sfn|Hell|Nešetřil|2008}}

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,{{sfn|Hell|Nešetřil|2008}} 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''.