Fuzzy Sets and Systems 128 (2002) 149–168 www.elsevier.com/locate/fss Fuzzy morphisms between graphs

A generic de.nition of fuzzy morphism between graphs (GFM) is introduced that includes classical graph related problem de.nitions as sub-cases (such as graph and subgraph isomorphism). The GFM uses a pair of fuzzy relations, one on the vertices and one on the edges. Each relation is a mapping between the elements of two graphs. These two fuzzy relations are linked with constraints derived from the graph structure and the notion of association graph. The theory extends the properties of fuzzy relation to the problem of generic graph correspondence. We introduce two complementary interpretations of GFM from which we derive several interesting properties. The.rst interpretation is the generalization of the notion of association compatibility. The second is the new notion of edge morphism. One immediate application is the introduction of several composition laws. Each property has a theoretical and a practical interpretation in the problem of graph correspondence that is explained throughout the paper. Special attention is paid to the formulation of a non-algorithmical theory in order to propose a.rst step towards a uni.ed theoretic framework for graph morphisms. c © 2002 Elsevier Science B.V. All rights reserved