• Source: Reeb graph

A Reeb graph (named after Georges Reeb by René Thom) is a mathematical object reflecting the evolution of the level sets of a real-valued function on a manifold.
According to a similar concept was introduced by G.M. Adelson-Velskii and A.S. Kronrod and applied to analysis of Hilbert's thirteenth problem. Proposed by G. Reeb as a tool in Morse theory, Reeb graphs are the natural tool to study multivalued functional relationships between 2D scalar fields



ψ


{\displaystyle \psi }

,



λ


{\displaystyle \lambda }

, and



ϕ


{\displaystyle \phi }

arising from the conditions




∇
ψ
=
λ
∇
ϕ


{\displaystyle \nabla \psi =\lambda \nabla \phi }

and



λ
≠
0


{\displaystyle \lambda \neq 0}

, because these relationships are single-valued when restricted to a region associated with an individual edge of the Reeb graph. This general principle was first used to study neutral surfaces in oceanography.
Reeb graphs have also found a wide variety of applications in computational geometry and computer graphics, including computer aided geometric design, topology-based shape matching, topological data analysis, topological simplification and cleaning, surface segmentation and parametrization, efficient computation of level sets, neuroscience, and geometrical thermodynamics.
In a special case of a function on a flat space (technically a simply connected domain), the Reeb graph forms a polytree and is also called a contour tree.
Level set graphs help statistical inference related to estimating probability density functions and regression functions, and they can be used in cluster analysis and function optimization, among other things.




Formal definition


Given a topological space X and a continuous function f: X → R, define an equivalence relation ~ on X where p~q whenever p and q belong to the same connected component of a single level set f−1(c) for some real c. The Reeb graph is the quotient space X /~ endowed with the quotient topology.
Generally, this quotient space does not have the structure of a finite graph. Even for a smooth function on a smooth manifold, the Reeb graph can be not one-dimensional and even non-Hausdorff space.
In fact, the compactness of the manifold is crucial: The Reeb graph of a smooth function on a closed manifold is a one-dimensional Peano continuum that is homotopy equivalent to a finite graph.
In particular, the Reeb graph of a smooth function on a closed manifold with a finite number of critical values –which is the case of Morse functions, Morse–Bott functions or functions with isolated critical points – has the structure of a finite graph.




Structure of the Reeb graph defined by a smooth function


Let



f
:
M
→


R




{\displaystyle f:M\to {\mathbb {R} }}

be a smooth function on a closed manifold



M


{\displaystyle M}

. The structure of the Reeb graph




R

f




{\displaystyle R_{f}}

depends both on the manifold



M


{\displaystyle M}

and on the class of the function



f


{\displaystyle f}

.




= The first Betti number of the Reeb graph

=
Since for a smooth function on a closed manifold, the Reeb graph




R

f




{\displaystyle R_{f}}

is one-dimensional, we consider only its first Betti number




b

1


(

R

f


)


{\displaystyle b_{1}(R_{f})}

; if




R

f




{\displaystyle R_{f}}

has the structure of a finite graph, then




b

1


(

R

f


)


{\displaystyle b_{1}(R_{f})}

is the cycle rank of this graph. An upper bound holds





b

1


(

R

f


)
≤
c
o
r
a
n
k
(

π

1


(
M
)
)


{\displaystyle b_{1}(R_{f})\leq corank(\pi _{1}(M))}

,
where



c
o
r
a
n
k
(

π

1


(
M
)
)


{\displaystyle corank(\pi _{1}(M))}

is the co-rank of the fundamental group of the manifold. If



dim
⁡
M
≥
3


{\displaystyle \dim M\geq 3}

, this bound is tight even in the class of simple Morse functions.
If



dim
⁡
M
=
2


{\displaystyle \dim M=2}

, for smooth functions this bound is also tight, and in terms of the genus



g


{\displaystyle g}

of the surface




M

2




{\displaystyle M^{2}}

the bound can be rewritten as





b

1


(

R

f


)
≤


{



g
,



if


M

2



is orientable





g

/

2
,



if


M

2



is non-orientable

.








{\displaystyle b_{1}(R_{f})\leq {\begin{cases}g,&{\text{if }}M^{2}{\text{ is orientable }}\\g/2,&{\text{if }}M^{2}{\text{ is non-orientable }}.\end{cases}}}


If



dim
⁡
M
=
2


{\displaystyle \dim M=2}

, for Morse functions, there is a better bound for the cycle rank. Since for Morse functions, the Reeb graph




R

f




{\displaystyle R_{f}}

is a finite graph, we denote by




N

2




{\displaystyle N_{2}}

the number of vertices with degree 2 in




R

f




{\displaystyle R_{f}}

. Then





b

1


(

R

f


)
≤


{



g
−

N

2


,



if


M

2



is orientable





(
g
−

N

2


)

/

2
,



if


M

2



is non-orientable

.








{\displaystyle b_{1}(R_{f})\leq {\begin{cases}g-N_{2},&{\text{if }}M^{2}{\text{ is orientable }}\\(g-N_{2})/2,&{\text{if }}M^{2}{\text{ is non-orientable }}.\end{cases}}}





= Leaf blocks of the Reeb graph

=
If



f
:
M
→
R


{\displaystyle f:M\to R}

is a Morse or Morse–Bott function on a closed manifold, then its Reeb graph




R

f




{\displaystyle R_{f}}

has the structure or a finite graph. This finite graph has a specific structure, namely

If



f


{\displaystyle f}

is Morse, then




R

f




{\displaystyle R_{f}}

has no loops, and all its leaf blocks are complete graphs




K

2




{\displaystyle K_{2}}

, i.e., closed intervals
If



f


{\displaystyle f}

is Morse–Bott, then




R

f




{\displaystyle R_{f}}

has no loops, and each its leaf block contains a vertex with degree at most 2




Description for Morse functions


If



f


{\displaystyle f}

is a Morse function with distinct critical values, the Reeb graph can be described more explicitly. Its nodes, or vertices, correspond to the critical level sets




f

−
1


(
c
)


{\displaystyle f^{-1}(c)}

. The pattern in which the arcs, or edges, meet at the nodes/vertices reflects the change in topology of the level set




f

−
1


(
t
)


{\displaystyle f^{-1}(t)}

as



t


{\displaystyle t}

passes through the critical value



c


{\displaystyle c}

. For example, if



c


{\displaystyle c}

is a minimum or a maximum of



f


{\displaystyle f}

, a component is created or destroyed; consequently, an arc originates or terminates at the corresponding node, which has degree 1. If



c


{\displaystyle c}

is a saddle point of index 1 and two components of




f

−
1


(
t
)


{\displaystyle f^{-1}(t)}

merge at



t
=
c


{\displaystyle t=c}

as



t


{\displaystyle t}

increases, the corresponding vertex of the Reeb graph has degree 3 and looks like the letter "Y". The same reasoning applies if the index of



c


{\displaystyle c}

is



d
i
m
X
−
1


{\displaystyle dimX-1}

and a component of




f

−
1


(
c
)


{\displaystyle f^{-1}(c)}

splits into two.




References

Kata Kunci Pencarian:

• Reeb graph
• Reeb
• Georges Reeb
• Topological data analysis
• René Thom
• Mapper
• Topological fluid dynamics
• Digital Morse theory
• Shape analysis (digital geometry)
• ICPRAM