  We present an algebraic approach to the watershed adapted to edge or node
weighted graphs. Starting with the flooding adjunction, we introduce the
flooding graphs, for which node and edge weights may be deduced one from the
other. Each node weighted or edge weighted graph may be transformed in a
flooding graph, showing that there is no superiority in using one or the other,
both being equivalent. We then introduce pruning operators extract subgraphs of
increasing steepness. For an increasing steepness, the number of never
ascending paths becomes smaller and smaller. This reduces the watershed zone,
where catchment basins overlap. A last pruning operator called scissor
associates to each node outside the regional minima one and only one edge. The
catchment basins of this new graph do not overlap and form a watershed
partition. Again, with an increasing steepness, the number of distinct
watershed partitions contained in a graph becomes smaller and smaller.
Ultimately, for natural image, an infinite steepness leads to a unique
solution, as it is not likely that two absolutely identical non ascending paths
of infinite steepness connect a node with two distinct minima. It happens that
non ascending paths of a given steepness are the geodesics of lexicographic
distance functions of a given depth. This permits to extract the watershed
partitions as skeletons by zone of influence of the minima for such
lexicographic distances. The waterfall hierarchy is obtained by a sequence of
operations. The first constructs the minimum spanning forest which spans an
initial watershed partition. The contraction of the trees into one node
produces a reduced graph which may be submitted to the same treatment. The
process is iterated until only one region remains. The union of the edges of
all forests produced constitutes a minimum spanning tree of the initial graph.
