Page 292 -

280 6 Stmctural Pattern Recognition

Two similar patterns will have a homomorphic relation in at least a large part of
their graph or tree representations. The two patterns will be structurally equivalent
if an isomorphism exists:

Figure 6.25. Two digraphs with two homomorphisms: (a) j( l)=a, J(2)=b, j(3)=c;
(b) f( l)=a,f(2)=c,J(3)=d.

The structural descriptions are then the same except for a node re-labelling
operation.
An algorithm for finding homomorphisms in two graphs GI=(Nl, R1) and
G2=(N2, R2) is based on the idea of first building the so-called match graph. This
is a graph where each node represents an assignment from one of the N1 nodes to
one of the N2 nodes. Let (nl,n2) and (q', nz') be two such assignments,
representing two distinct nodes in the match graph. An arc exists between these
two nodes if the assignments are compatible or, equivalently, if the relation for the
node pair (n, , nl ') is the same as for the node pair (n, , n,') .

Figure 6.26. Match graph for the two graphs shown in Figure 6.25. The
homomorphisms are shown with solid line.