In several fields of Image Processing (e.g. geography, histology, 2-D electrophoretic gels), the space turns out to be partitioned into zones whose neighborhood relationships are of interest. More generally, a great number of phenomena may be modelled by graphs. Now, a graph being a lattice, it can be approached by Mathematical Morphology. This is the purpose of the present study: after introducing the theoretical framework, it deals with various graphs that can be defined on a given set of objects, depending on the intensity of the desirable relationships (e.g. Delaunay triangulations., Gabriel graphs, Relative neighborhood graphs...). The computational aspect is especially emphasized and new digital algorithms, based on Euclidean zones of influence, are introduced. The main operators. of Mathematical Morphology are then defined and implemented for graphs (erosions and dilations, morphological. filters, distance function, skeletons, labelling, geodesic operators, reconstruction, etc...) in both binary and decimal cases. A series of fast computational algorithms is developed, leading to a complete software package.