Count Riba

Rib's graph functions of height on a torus. The critical levels of the function correspond to the vertices of the graph, and the connected component of the nonsingular level corresponds to a point on the edge. The orientation of the graph is determined by the direction of growth of the function.

In graph theory , a Reeb graph of some function describes the connectedness of the level surfaces of this function. Introduced by George Ribs ^[1]

Content

Definition

Consider a continuous function defined on a compact manifold , $f:M\to R$ ${\ displaystyle f: M \ to R}$ . Prototype of a point $y\in R$ ${\ displaystyle y \ in R}$ is a function level surface $f^{-1}(y)\subset M$ ${\ displaystyle f ^ {- 1} (y) \ subset M}$ . Two points $x,x'\in M$ ${\ displaystyle x, x '\ in M}$ are called equivalent $x\!\sim x'$ ${\ displaystyle x \! \ sim x '}$ if they belong to the same connected component of the level surface $f^{-1}(y)$ ${\ displaystyle f ^ {- 1} (y)}$ .

Riba count function $f$ ${\ displaystyle f}$ Is a factor space of diversity $M$ ${\ displaystyle M}$ by such an equivalence relation , $G=M/\!\sim$ ${\ displaystyle G = M / \! \ sim}$ . The vertices of the graph are the connected components of the critical levels of the function. Graph orientation $G$ ${\ displaystyle G}$ determined by the direction of the gradient of the function $f$ ${\ displaystyle f}$ .

Properties

The following properties of Count Reeb were proved in his fundamental work ^[1] :

Let on compact $n$ ${\ displaystyle n}$ -dimensional variety of smoothness class $C^{2}$ ${\ displaystyle C ^ {2}}$ a Morse function f is given , all critical points of which correspond to different critical values of the function. The set of such functions is open and dense in the space of all functions. We denote $\Gamma$ ${\ displaystyle \ Gamma}$ Rib's graph of this function. Then:

Vertices of degree 1 of the graph $\Gamma$ ${\ displaystyle \ Gamma}$ the critical points of the function f of index 0 and n correspond exactly.
If a $n\geq 3$ ${\ displaystyle n \ geq 3}$ , the vertex of the graph corresponding to the critical level of the function f , which contains the critical point of index 1 and n-1 , can have degree 2 or 3 .
If a $n\,=2$ ${\ displaystyle n \, = 2}$ , the vertices of the graph corresponding to the critical points of index 1 can have degree 2 , 3, or 4 .
The degree of the vertex of the graph corresponding to the critical level of the function f , which contains the critical point of the index other than 0 , 1 , n-1 and n , is always 2 .

These graph properties entail the curious property of Morse functions, proved there ^[1] :

Denote by $\Omega _{k}$ ${\ displaystyle \ Omega _ {k}}$ the set of critical points of the index function k and nk . If a $n\geq 3$ ${\ displaystyle n \ geq 3}$ then $|\Omega _{0}|\leq |\Omega _{1}|+2$ ${\ displaystyle | \ Omega _ {0} | \ leq | \ Omega _ {1} | +2}$ .

Application

Reeb graphs are used in mathematics when studying

topological classification of Morse functions ^[2]
Hamiltonian systems ^[3]

RIBA graphs and, in particular, RIBA acyclic graphs, called contour trees , are widely used in computer applications:

in computer design and geometric modeling,
in geometric models of data structures and database search methods
in automation systems for design work .

Notes

↑ ¹ ² ³ G. Reeb , Sur les points singuliers d'une forme de Pfaff complétement intégrable ou d'une fonction numérique. - CRAS Paris 222, 1946, pp. 847-849. [one]
↑ Sharko V.V. Smooth and topological equivalence of functions on surfaces. // Ukrainian Mathematical Journal. 2003. V. 55. No. 5. P. 687-700.
↑ A. V. Bolsinov, A. T. Fomenko, Introduction to the topology of integrable Hamiltonian systems, Nauka, Moscow, 1997.

[Reeb-1] ¹ ² ³ G. Reeb , Sur les points singuliers d'une forme de Pfaff complétement intégrable ou d'une fonction numérique. - CRAS Paris 222, 1946, pp. 847-849. [one]

[2] Sharko V.V. Smooth and topological equivalence of functions on surfaces. // Ukrainian Mathematical Journal. 2003. V. 55. No. 5. P. 687-700.

[3] A. V. Bolsinov, A. T. Fomenko, Introduction to the topology of integrable Hamiltonian systems, Nauka, Moscow, 1997.