The matrix Z = (z*irjs*) with

$$z_{i r j s}=\left\{\begin{array}{c c c}{{\epsilon}}&{{:}}&{{(i j,r s)\in\overline{{{E}}}(Z)}}\\ {{\kappa_{i j r s}}}&{{:}}&{{\mathrm{otherwise}}}\end{array}\right.$$

assigns weights to the vertices and edges of Z. Note that an association graph assigns realvalued weights to both, its vertices and edges. This is in contrast to standard association graph formulations, where Z is either unweighted (constant weights) or weights are assigned to vertices only.

## 3.3 A Necessary And Sufficient Condition

In this subsection, we show that p-closure of M is a necessary and sufficient condition for the desired equivalence between graph matching and clique search in an association graph. Note that equivalence means that there is a bijective mapping Φ : CZ → M
with ω(C) = fΦ(C)for all cliques C ∈ CZ. The mapping Φ then induces a one-to-one correspondence between the maximum (maximal) cliques in Z and the global (local)
optimal solutions from M. Theorem 1. Let X and Y be graphs. Then the GMP (5) of X and Y *is equivalent to* the MWCP in a κ-association graph Z = X  Y *if, and only if, there is a property* p on IXY such that the search space M of (5) is the set of all p*-morphisms from* MXY .

Proof: The ⇒ - direction is trivial. Suppose that GMP (5) is equivalent to the MWCP
in Z. Then we simply define the property p with i ∼p r if there is a morphism φ ∈ M
with i φ = r.

Now let us show the opposite direction. Suppose that there is a property p on IXY
such that M is the set of all p-morphisms from MXY . We want to show that there is a bijection Φ : CZ → M, C 7→ φC
such that ω(C) = f(φC*, X, Y* ) for all C ∈ CZ. With each clique C ∈ CZ we associate a partial morphism φC : V (X) → V (Y ) such that φC(i) = r for all (*i, r*) ∈ C. We show that φC is a feasible morphism from M. Let *i, j* ∈ V (X) and *r, s* ∈ V (Y ) be vertices with φC(i) = r and φC(j) = s. By construction, (*i, r*) and (*j, s*) are members of clique C. Since Z[C] is complete, there is an edge incident with (*i, r*) and (*j, s*). Hence, (i, r) ∼p (*j, s*)
and, therefore, Γ(φC) ⊆ RpXY . Since M is p-closed, we have φC ∈ M.

Similarly, with each morphism φ ∈ M we associate a subset Cφ of V (Z) with
(*i, j*) ∈ Cφ ⇔ φ(i) = j or φ(j) = i.

Since φ is a feasible p-morphism, Cφ is a clique in Z. It is straightforward to show that both associations give rise to well-defined mappings

$$\begin{array}{l l}{{\Phi:{\mathcal{C}}_{Z}\to{\mathcal{M}},}}&{{C\mapsto\phi_{C}}}\\ {{\Psi:{\mathcal{M}}\to{\mathcal{C}}_{Z},}}&{{\phi\mapsto C_{\phi}.}}\end{array}$$
