Geodesic
A multicolour graph as a complete topological invariant for $\Omega$-stable flows without periodic trajectories on surfaces
Sbornik. Mathematics, Tome 209 (2018) no. 1, pp. 96-121 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Studying the dynamics of a flow on surfaces by partitioning the phase space into cells with the same limit behaviour of trajectories within a cell goes back to the classical papers of Andronov, Pontryagin, Leontovich and Maier. The types of cells (the number of which is finite) and how the cells adjoin one another completely determine the topological equivalence class of a flow with finitely many special trajectories. If one trajectory is chosen in every cell of a rough flow without periodic orbits, then the cells are partitioned into so-called triangular regions of the same type. A combinatorial description of such a partition gives rise to the three-colour Oshemkov-Sharko graph, the vertices of which correspond to the triangular regions, and the edges to separatrices connecting them. Oshemkov and Sharko proved that such flows are topologically equivalent if and only if the three-colour graphs of the flows are isomorphic, and described an algorithm of distinguishing three-colour graphs. But their algorithm is not efficient with respect to graph theory. In the present paper, we describe the dynamics of $\Omega$-stable flows without periodic trajectories on surfaces in the language of four-colour graphs, present an efficient algorithm for distinguishing such graphs, and develop a realization of a flow from some abstract graph. Bibliography: 17 titles.
Keywords: multicolour graph, topological invariant, $\Omega$-stable flow
Mots-clés : efficient algorithm. 
@article{SM_2018_209_1_a4,
     author = {V. E. Kruglov and D. S. Malyshev and O. V. Pochinka},
     title = {A~multicolour graph as a~complete topological invariant for $\Omega$-stable flows without periodic trajectories on surfaces},
     journal = {Sbornik. Mathematics},
     pages = {96--121},
     year = {2018},
     volume = {209},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2018_209_1_a4/}
}
TY  - JOUR
AU  - V. E. Kruglov
AU  - D. S. Malyshev
AU  - O. V. Pochinka
TI  - A multicolour graph as a complete topological invariant for $\Omega$-stable flows without periodic trajectories on surfaces
JO  - Sbornik. Mathematics
PY  - 2018
SP  - 96
EP  - 121
VL  - 209
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SM_2018_209_1_a4/
LA  - en
ID  - SM_2018_209_1_a4
ER  - 
%0 Journal Article
%A V. E. Kruglov
%A D. S. Malyshev
%A O. V. Pochinka
%T A multicolour graph as a complete topological invariant for $\Omega$-stable flows without periodic trajectories on surfaces
%J Sbornik. Mathematics
%D 2018
%P 96-121
%V 209
%N 1
%U http://geodesic.mathdoc.fr/item/SM_2018_209_1_a4/
%G en
%F SM_2018_209_1_a4
V. E. Kruglov; D. S. Malyshev; O. V. Pochinka. A multicolour graph as a complete topological invariant for $\Omega$-stable flows without periodic trajectories on surfaces. Sbornik. Mathematics, Tome 209 (2018) no. 1, pp. 96-121. http://geodesic.mathdoc.fr/item/SM_2018_209_1_a4/

[1] V. E. Alekseev, V. A. Talanov, Grafy i algoritmy. Struktury dannykh. Modeli vychislenii, Izd-vo «Internet-universitet informatsionnykh tekhnologii», M., 2006, 320 pp.

[2] A. Andronov, L. Pontrjagin, “Systèmes grossiers”, C. R. Acad. Sci. URSS (2), 14 (1937), 247–250 | Zbl

[3] A. Cobham, “The intrinsic computational difficulty of functions”, Logic, methodology, and philosophy of science, Proceedings of the 1964 international congress, North-Holland, Amsterdam, 1965, 24–30 | MR | Zbl

[4] V. Z. Grines, S. H. Kapkaeva, O. V. Pochinka, “A three-colour graph as a complete topological invariant for gradient-like diffeomorphisms of surfaces”, Sb. Math., 205:10 (2014), 1387–1412 | DOI | DOI | MR | Zbl

[5] V. Z. Grines, T. V. Medvedev, O. V. Pochinka, Dynamical systems on $2$- and $3$-manifolds, Dev. Math., 46, Springer, Cham, 2016, xxvi+295 pp. | DOI | MR

[6] M. R. Garey, D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979, x+338 pp. | MR | MR | Zbl | Zbl

[7] D. König, “Grafok es matrixok”, Mat. Fiz. Lapok, 38 (1931), 116–119 | Zbl

[8] E. Leontovič, A. G. Mayer, “Sur les trajectoires qui déterminent la structure qualitative de la division de la sphère en trajectoires”, C. R. Acad. Sci. URSS (2), 14 (1937), 251–254 | Zbl

[9] E. A. Leontovich, A. G. Maier, “O skheme, opredelyayuschei topologicheskuyu strukturu razbieniya na traektorii”, Dokl. AN SSSR, 103:4 (1955), 557–560 | MR | Zbl

[10] A. G. Maier, “Grubye preobrazovaniya okruzhnosti”, Uch. zap. GGU, 12, GGU, Gorkii, 1939, 215–229

[11] G. Miller, “Isomorphism testing for graphs of bounded genus”, STOC' 80 Proceedings of the 12th annual ACM symposium on theory of computing, Los Angeles, CA, 1980, ACM, New York, 1980, 225–235 | DOI

[12] D. Neumann, T. O'Brien, “Global structure of continuous flows on 2-manifolds”, J. Differential Equations, 22:1 (1976), 89–110 | DOI | MR | Zbl

[13] A. A. Oshemkov, V. V. Sharko, “Classification of Morse–Smale flows on two-dimensional manifolds”, Sb. Math., 189:8 (1998), 1205–1250 | DOI | DOI | MR | Zbl

[14] J. Palis, Jr., W. de Melo, Geometric theory of dynamical systems. An introduction, Springer-Verlag, New York–Berlin, 1982, xii+198 pp. | MR | MR | Zbl

[15] M. M. Peixoto, “On the classification of flows on 2-manifolds”, Dynamical systems (Univ. Bahia, Salvador, 1971), Academic Press, New York, 1973, 389–419 | MR | Zbl

[16] C. Pugh, M. Shub, “The $\Omega$-stability theorem for flows”, Invent. Math., 11:2 (1970), 150–158 | DOI | MR | Zbl

[17] C. Robinson, Dynamical systems. Stability, symbolic dynamics, and chaos, Stud. Adv. Math., CRC Press, Boca Raton, FL, 1995, xii+468 pp. | MR | Zbl