This dissertation presents new approximation algorithms and an exact approach to the solution of an inexact graph matching problem. The problem consists in finding the best match between a generic model graph and a graph representing an image, the latter with more nodes than the former. The motivation for studying this problem comes from a scene recognition problem, which consists in characterizing objects involved in a given scene and the relationships between them. An application of this problem appears in the analysis of medical images and consists in recognizing 3-dimensional structures in the human brain using images obtained by magnetic resonance. Such images must be previously processed by an automatic segmentation method and the recognition process consists in the search of an structural matching between the image and a generic model, typically defined as an atlas of medical images. New heuristics are proposed, such as a greedy randomized construction algorithm, a path relinking procedure and a GRASP heuristic that combines them with a local search technique. Furthermore, an original integer formulation of the problem based on integer multicommodity flows is proposed, which makes possible the exact solution of medium- sized instances.