An Algorzthm for Subgraph Isomorphism
33
record which column has been selected at which depth. H~ = k if the kth column has
been selected at depth d.
We shall use the symbol := to denote assignment. Thus d := d + 1 means "set d
equal to d + 1." Further, we shall write M := Md, meaning "set the entire matrix M
equal to matrix Md ." Matrix M~ is a stored copy of matrix M at depth d. We have for-
mulated the algorithm so that it is as similar as possible to the algorithm of Section 3
(for instance the complete assignment Md := M is not really necessary in the present
section).
The simple enumeration algorithm is as follows.
Step
1 M = M °, d "=
1; H1 = 0;
for allz = 1, .. , p, , set F, .= 0;
Step2 If there is no value of 3 such that md~ = landF~ = 0 then go to step 7;
Md = M,
ifd = 1 thent .= Hi elsek .= 0,
Step3 k '= k + 1,
ff mdk = 0 or Fk = 1 then go to step 3;
for all .7 # /~ set mdj := 0,
Step 4. If d < p. then go to step 6 else use condition (1) and give output if an isomorphism is found;
Step5 If therelsno3 >ksuchthatnmdj = landF: = 0 then go to step 7;
M .=Ma,
go to step 3;
Step6 H~ = k, Fk = 1; d =d+ 1;
go to step 2,
Step 7 If d = 1 then terminate algorithm,
Fk =0;
d.=d- 1, M =M,~, k.=H,t,
go to step 5,
3. Algorzthm Employzng Refinement Procedure
To reduce the amount of computation required for finding subgraph isomorphisms we
employ a procedure, which we call the
refinement procedure,
that eliminates some of the
l's from the matrices
M,
thus eliminating successor nodes m the tree search.
To introduce the refinement procedure, let us consider the matrix M that is associated
with any given nonterminal node in the search tree. Any subgraph isomorphism corre-
sponds to a particular matrix M'. We say that an isomorphism is an isomorphism
under
M if its terminal node in the search tree is a successor of the node with which M is asso-
ciated. The O's in the matrix M merely preclude correspondences between points of V.
f
and V~. If m,j = 0 for all lsomorphlsms under M, then if m. = 1 we can change m. = 1
to m. = 0 without losing any of the isomorphisms under M: all such isomorphisms will
still be found by the tree search. In the next paragraph we work out a condition that is
necessardy satisfied if m:~ = 1 for any isomorphisms under M. If this necessary condi-
tion is not satisfied and m. = 1, then the refinement procedure changes
m.
= 1 to
m,j = O.
Let v~, be the ith point in V~, and let v~ be the 3th point in V~. Let
{v.1, - • • , v.~, • • , v.~} be the set of all points of G. that are adjacent to v.~ in g.. Let
us consider the matrix M' that is associated ~ith any given isomorphism under M. From
the definition of subgraph isomorphism it is necessary that if v.~ corresponds to vt~ in
the isomorphism, then for each x = 1, .-. , ~ there must exist a point ray in V~ that is
adjacent to v~j, such that v~y corresponds to v.~ in the isomorphism. If v~v corresponds
to v.~ in the isomorphism, then the element of M' that corresponds to Iv.~, v~v} is 1.
Therefore if v.~ corresponds to v~j in
any
isomorphism under M, then for each
x = 1, .. , ~ there must be a 1 in M corresponding to some {v.~, v~y} such that va~ is
adjacent to vt~ • In other words, ff v.~ corresponds to v~j in any isomorphism under M,
then
(Vx) ((a,, = 1) ~ (~y)
(m,~.b~, =
1)). (2)
剩余12页未读，继续阅读
