Editing Graph homomorphism (section)

==Connection to constraint satisfaction problems==
===Examples===
[[File:Graph of non-adjacent weekdays.svg|thumb|Graph ''H'' of non-consecutive weekdays, isomorphic to the [[complement graph]] of ''C''<sub>7</sub> and to the [[circular clique]] ''K''<sub>7/2</sub>]]
Some scheduling problems can be modeled as a question about finding graph homomorphisms.{{sfn|Cameron|2006|p=1}}{{sfn|Hell|Nešetřil|2004|loc=§1.8}} As an example, one might want to assign workshop courses to time slots in a calendar so that two courses attended by the same student are not too close to each other in time. The courses form a graph ''G'', with an edge between any two courses that are attended by some common student. The time slots form a graph ''H'', with an edge between any two slots that are distant enough in time. For instance, if one wants a cyclical, weekly schedule, such that each student gets their workshop courses on non-consecutive days, then ''H'' would be the [[complement graph]] of ''C''<sub>7</sub>. A graph homomorphism from ''G'' to ''H'' is then a schedule assigning courses to time slots, as specified.{{sfn|Cameron|2006|p=1}} To add a requirement saying that, e.g., no single student has courses on both Friday and Monday, it suffices to remove the corresponding edge from ''H''.

A simple [[frequency allocation]] problem can be specified as follows: a number of transmitters in a [[wireless network]] must choose a frequency channel on which they will transmit data. To avoid [[Electromagnetic interference|interference]], transmitters that are geographically close should use channels with frequencies that are far apart. If this condition is approximated with a single threshold to define 'geographically close' and 'far apart', then a valid channel choice again corresponds to a graph homomorphism. It should go from the graph of transmitters ''G'', with edges between pairs that are geographically close, to the graph of channels ''H'', with edges between channels that are far apart. While this model is rather simplified, it does admit some flexibility: transmitter pairs that are not close but could interfere because of geographical features can be added to the edges of ''G''. Those that do not communicate at the same time can be removed from it. Similarly, channel pairs that are far apart but exhibit [[harmonic]] interference can be removed from the edge set of ''H''.{{sfn|Hell|Nešetřil|2004|pp=30–31}}

In each case, these simplified models display many of the issues that have to be handled in practice.{{sfn|Hell|Nešetřil|2004|pp=31–32}} [[Constraint satisfaction problem]]s, which generalize graph homomorphism problems, can express various additional types of conditions (such as individual preferences, or bounds on the number of coinciding assignments). This allows the models to be made more realistic and practical.

===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''.