Catalogue of Artificial Intelligence Techniques
Graph Matching
Keywords: Relational structures, double subgraph isomorphism, graph isomorphism, matching
Categories: Natural Language , Vision
Author(s): H.W. Hughes
Relational structures are often represented as graphs with nodes connected by labelled arcs. The problem of matching two such structures is known as graph matching and can be achieved in a number of ways. Firstly a one-to-one mapping can be achieved between the nodes and arcs of each of the two graphs. This is known as graph isomorphism. Alternatively a one-to-one mapping can be achieved between one graph and a subgraph of the other. This is known as double subgraph isomorphism. Sometimes a perfect mapping between graphs is not required, some arcs and nodes being considered unimportant and omitted from the matching process.
References:
- Harary, F., Graph Theory
, Addison-Wesley , Reading, Mass., 1969.
Comments:
No comments.