J. Maxwell, On Hills and Dales, Philosophical Magazine, vol.440, pp.421-427, 1870.
DOI : 10.1017/CBO9780511710377.018

C. Jordan, Nouvelles observations sur les lignes de fa??tesfa??tes et de thalweg, Comptes Rendus des Séances de l'Académie des Sciences, pp.1023-1025, 1872.

S. Beucher and C. , Use of watersheds in contour detection, Procs. of the International Workshop on Image Processing Real-Time Edge and Motion Detection/Estimation, 1979.

F. Meyer, Un algorithme optimal de ligne de partage des eaux, Procs. of 8` eme Congrès AFCET, pp.847-859, 1991.

L. Vincent and P. Soille, Watersheds in digital spaces: an efficient algorithm based on immersion simulations, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.13, issue.6, pp.583-598, 1991.
DOI : 10.1109/34.87344

S. Beucher and F. Meyer, The morphological approach to segmentation: the watershed transformation, Mathematical Morphology in Image Processing, pp.443-481, 1993.

M. Couprie and G. Bertrand, Topological grayscale watershed transform, Procs. of SPIE Vision Geometry V, pp.136-146, 1997.

G. Bertrand, On Topological Watersheds, Journal of Mathematical Imaging and Vision, vol.34, issue.6, pp.217-230, 2005.
DOI : 10.1007/s10851-005-4891-5
URL : https://hal.archives-ouvertes.fr/hal-00622398

M. Couprie, L. Najman, and G. Bertrand, Quasi-Linear Algorithms for the Topological Watershed, Journal of Mathematical Imaging and Vision, vol.13, issue.6, pp.231-249, 2005.
DOI : 10.1007/s10851-005-4892-4
URL : https://hal.archives-ouvertes.fr/hal-00622399

L. Najman, M. Couprie, and G. Bertrand, Watersheds, mosaics, and the emergence paradigm, Discrete Applied Mathematics, vol.147, issue.2-3, pp.301-324, 2005.
DOI : 10.1016/j.dam.2004.09.017
URL : https://hal.archives-ouvertes.fr/hal-00622113

F. Meyer, Minimum Spanning Forests for Morphological Segmentation, Procs. of the second international conference on Mathematical Morphology and its Applications to Image Processing, pp.77-84, 1994.
DOI : 10.1007/978-94-011-1040-2_11

A. X. Falcão, J. Stolfi, R. De-alencar, and . Lotufo, The image foresting transform: theory, algorithms, and applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.26, issue.1, pp.19-29, 2004.
DOI : 10.1109/TPAMI.2004.1261076

R. Lotufo and A. Falcão, The Ordered Queue and the Optimality of the Watershed Approaches, Procs. of the 5th International Symposium on Mathematical Morphology, pp.341-350, 2000.
DOI : 10.1007/0-306-47025-X_37

J. K. Udupa and S. Samarsekara, Fuzzy Connectedness and Object Definition: Theory, Algorithms, and Applications in Image Segmentation, Graphical Models and Image Processing, vol.58, issue.3, pp.246-261, 1996.
DOI : 10.1006/gmip.1996.0021

P. K. Saha and J. K. Udupa, Relative Fuzzy Connectedness among Multiple Objects: Theory, Algorithms, and Applications in Image Segmentation, Computer Vision and Image Understanding, vol.82, issue.1, pp.42-56, 2001.
DOI : 10.1006/cviu.2000.0902

T. Kong and A. Rosenfeld, Digital topology: Introduction and survey, Computer Vision, Graphics, and Image Processing, vol.48, issue.3, pp.357-393, 1989.
DOI : 10.1016/0734-189X(89)90147-3

F. Meyer, Topographic distance and watershed lines, Signal Processing, vol.38, issue.1, pp.113-125, 1993.
DOI : 10.1016/0165-1684(94)90060-4

L. Najman and M. Schmitt, Watershed of a continuous function, Signal Processing, vol.38, issue.1, pp.68-86, 1993.
DOI : 10.1016/0165-1684(94)90059-0
URL : https://hal.archives-ouvertes.fr/hal-00622129

P. Soille and C. Gratin, An Efficient Algorithm for Drainage Network Extraction on DEMs, Journal of Visual Communication and Image Representation, vol.5, issue.2, pp.181-189, 1994.
DOI : 10.1006/jvci.1994.1017

J. B. Roerdink and A. Meijster, The watershed transform: Definitions, algorithms and parallelization strategies, Fundamenta Informaticae, vol.41, issue.12, pp.187-228, 2001.

J. Cousty, G. Bertrand, L. Najman, and M. Couprie, The drop of water principle: comparison of classical watershed algorithms

J. Nesetril, E. Milková, and H. Nesetrilová, Otakar Bor??vka on minimum spanning tree problem Translation of both the 1926 papers, comments, history, Discrete Mathematics, vol.233, issue.1-3, pp.3-36, 2001.
DOI : 10.1016/S0012-365X(00)00224-7

R. Prim, Shortest connection networks and some generalizations, Bell Syst, Tech. J, vol.36, pp.1389-1401, 1957.
DOI : 10.1002/j.1538-7305.1957.tb01515.x

R. L. Graham and P. Hell, On the History of the Minimum Spanning Tree Problem, IEEE Annals of the History of Computing, vol.7, issue.1, pp.43-57, 1985.
DOI : 10.1109/MAHC.1985.10011

C. Zahn, Graph-theoretical methods for detecting and descibing gestalt clusters, IEEE Transactions on Computers C, vol.20, issue.1, pp.99-112, 1971.

T. H. Cormen, C. Leiserson, and R. Rivest, Introduction to algorithms, 2001.

B. Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the ACM, vol.47, issue.6, pp.1028-1047, 2000.
DOI : 10.1145/355541.355562

A. N. Moga, T. Viero, M. Gabbouj, M. Nölle, G. Schreiber et al., Parallel watershed algorithm based on sequential scanning, Procs. of IEEE Workshop on Nonlinear Signal and Image Processing, 1995.

J. Cousty, M. Couprie, L. Najman, and G. Bertrand, Grayscale Watersheds on Perfect Fusion Graphs, Procs. of the 11th International Workshop on Combinatorial Image Analysis, pp.60-73, 2006.
DOI : 10.1007/11774938_6
URL : https://hal.archives-ouvertes.fr/hal-00622038

R. Audigier and R. A. Lotufo, Duality between the Watershed by Image Foresting Transform and the Fuzzy Connectedness Segmentation Approaches, 2006 19th Brazilian Symposium on Computer Graphics and Image Processing, pp.53-60, 2006.
DOI : 10.1109/SIBGRAPI.2006.14

G. Bertrand, On the dynamics, Image and Vision Computing to appear

A. Rosenfeld, On connectivity properties of grayscale pictures, Pattern Recognition, vol.16, issue.1, pp.47-50, 1983.
DOI : 10.1016/0031-3203(83)90007-9

J. K. Udupa, P. K. Saha, and R. A. Lotufo, Relative fuzzy connectedness and object definition: theory, algorithms, and applications in image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.24, issue.11, pp.1485-1500, 2002.
DOI : 10.1109/TPAMI.2002.1046162

J. Cousty, G. Bertrand, M. Couprie, and L. Najman, Fusion graphs: merging properties and watershed, submitted. Also in technical report, pp.2005-2009, 2006.
DOI : 10.1007/s10851-007-0047-0
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.219.1082

J. Cousty, G. Bertrand, M. Couprie, and L. Najman, Fusion Graphs, Region Merging and Watersheds, Procs. of the 13th International Conference on Discrete Geometry for Computer Imagery, pp.343-354, 2006.
DOI : 10.1007/11907350_29
URL : https://hal.archives-ouvertes.fr/hal-00622035

P. K. Saha, J. K. Udupa, and D. Odhner, Scale-Based Fuzzy Connected Image Segmentation: Theory, Algorithms, and Validation, Computer Vision and Image Understanding, vol.77, issue.2, pp.145-174, 2000.
DOI : 10.1006/cviu.1999.0813

Y. Zhuge, J. K. Udupa, and P. K. Saha, Vectorial scale-based fuzzy-connected image segmentation, Computer Vision and Image Understanding, vol.101, issue.3, pp.177-193, 2006.
DOI : 10.1016/j.cviu.2005.07.009

R. Deriche, Using Canny's criteria to derive a recursively implemented optimal edge detector, International Journal of Computer Vision, vol.1, issue.2, pp.167-187, 1987.
DOI : 10.1007/BF00123164

J. Serra and L. Vincent, An overview of morphological filtering, Circuits Systems Signal Process, vol.11, issue.1, pp.48-107, 1992.

E. Breen and R. Jones, Attribute Openings, Thinnings, and Granulometries, Computer Vision and Image Understanding, vol.64, issue.3, pp.377-389, 1996.
DOI : 10.1006/cviu.1996.0066

L. Najman and M. Couprie, Building the Component Tree in Quasi-Linear Time, IEEE Transactions on Image Processing, vol.15, issue.11, pp.3531-3539, 2006.
DOI : 10.1109/TIP.2006.877518
URL : https://hal.archives-ouvertes.fr/hal-00622110

P. Soille, Morphological Image Analysis, 1999.

J. Cousty, L. Najman, G. Bertrand, and M. Couprie, Minimum spanning tree by watershed in preparation

L. Najman and M. Schmitt, Geodesic saliency of watershed contours and hierarchical segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.18, issue.12, pp.1163-1173, 1996.
DOI : 10.1109/34.546254
URL : https://hal.archives-ouvertes.fr/hal-00622128

P. Proof, We will prove that for any point x 0 in V , there exists in X a path from x 0 to M (F ) which is a path with steepest descent for F . Thus, by Lem. 9, this will establish the first part of Prop. 13. From Lem. 9, it may be seen that there exists in X an M-path (for H), denoted by ? = x 0 , . . . , x l , which is a path with steepest descent for H. By Lem. 42.ii, ? is a path with steepest descent for F . Since x l is a vertex of M (H), by Lem. 42.i, there exists in M (H) a path ? ? = x l , . . . , x m from x l to M (F ) which is a path with steepest descent for F . Since X is an extension of, M (H) ? X. Hence

?. Let-i, P i?1 ) holds. By Prop. 18 and Lem. 41, (P i?1 ) implies that X i?1 is a forest relative to M (F ) Therefore, it follows from Lem. 45, that the altitude (for F ) of any edge of G outgoing from X i?1 is greater than or equal to F (u i ) By construction of F i?1

B. Proof-of-th, Suppose that Y is a MSF relative to X. Suppose also that there exist A and B, two components of X such that

?. (. Since and B. ?. , ) and such that x k (resp. x l ) is the only vertex of A ? (resp. B ? ) in ?. Notice that {x k , x k+1 } and {x l?1 , x k (resp. ? B = x l , . . . , x m ) be a simple path in A ? (resp. B ? ), such that x 0 (resp. x m ) is the only point of ? A (resp. ? B ) which is a point of A (resp. B) Since ? ? = x 0 Without loss of generality, Thus, since F (?) < F (A, B), we have either F (? A )