×

On algorithms that effectively distinguish gradient-like dynamics on surfaces. (English) Zbl 1435.37029

Summary: In the present paper we survey existing graph invariants for gradient-like flows on surfaces up to the topological equivalence and develop effective algorithms for their distinction (let us recall that a flow given on a surface is called a gradient-like flow if its non-wandering set consists of a finite set of hyperbolic fixed points, and there is no trajectories connecting saddle points). Additionally, we construct a parametrized algorithm for the Fleitas’s invariant, which will be of linear time, when the number of sources is fixed. Finally, we prove that the classes of topological equivalence and topological conjugacy are coincide for gradient-like flows, so, all the proposed invariants and distinguishing algorithms works also for topological classification, taking in sense time of moving along trajectories. So, as the main result of this paper we have got multiple ways to recognize equivalence and conjugacy class of arbitrary gradient-like flow on a closed surface in a polynomial time.

MSC:

37B35 Gradient-like behavior; isolated (locally maximal) invariant sets; attractors, repellers for topological dynamical systems
37E30 Dynamical systems involving homeomorphisms and diffeomorphisms of planes and surfaces
37C15 Topological and differentiable equivalence, conjugacy, moduli, classification of dynamical systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andronov, A.A., Pontryagin, L.S.: Rough systems. Doklady Akademii Nauk SSSR 14(5), 247-250 (1937). (in Russian) · Zbl 0016.11301
[2] Aho, A.V., Corasick, M.J.: Efficient string matching: An aid to bibliographic search. Commun ACM. 18(6), 333-340 (1975) · Zbl 0301.68048
[3] Apostolico, A., Giancarlo, R.: The Boyer-Moore-Galil string searching strategies revisited. SIAM J Comput 15(1), 98-105 (1986) · Zbl 0589.68047 · doi:10.1137/0215007
[4] Cobham, A.: The intrinsic computational difficulty of functions. In: Proc 1964 International Congress for Logic, Methodology, and Philosophy of Science, pp. 24-30. North-Holland, Amsterdam (1964)
[5] Donald, K., Morris, J.H., Vaughan, P.: Fast pattern matching in strings. SIAM J Comput 6(2), 323-350 (1977) · Zbl 0372.68005 · doi:10.1137/0206024
[6] Fleitas, G.: Classification of gradiet-like flows on dimensions two and three. Bol. Soc. Bras. Mat. 6, 155-183 (1975) · Zbl 0383.58013 · doi:10.1007/BF02584782
[7] Galil, Z., Hoffmann, C., Schnorr, C., Weber, A.: An \[O(n^3log n)O\](n3logn) deterministic and an \[O(n^3)O\](n3) Las Vegas isomorphism test for trivalent graphs. J. ACM 34, 513-531 (1987) · doi:10.1145/28869.28870
[8] Grines, V., Medvedev, T., Pochinka, O.: Dynamical Systems on 2- and 3-Manifolds. Springer, Basel (2016) · Zbl 1417.37018 · doi:10.1007/978-3-319-44847-3
[9] Hopcroft, J.E., Wong, J.K.: Linear time algorithm for isomorphism of planar graphs: preliminary report. In: Proceedings of the 6th Annual ACM Symposium on Theory of Computing, Seattle, Wash., pp. 172-184 (1974) · Zbl 0369.05028
[10] Kawarabayashi, K.: Graph isomorphism for bounded genus graphs in linear time (2015). arXiv:1511.02460
[11] Kruglov, V.: Topological conjugacy of gradient-like flows on surfaces. Dinamicheskie sistemy 8(36)(1), 15-21 (2018) · Zbl 1407.37041
[12] Kruglov, V.E., Malyshev, D.S., Pochinka, O.V.: A multicolour graph as a complete topological invariant for \[\Omega\] Ω-stable flows without periodic trajectories on surfaces. Sb. Math. 209(1), 96-121 (2018a). https://doi.org/10.1070/SM8797 · Zbl 1392.37021 · doi:10.1070/SM8797
[13] Kruglov, V.E., Malyshev, D.S., Pochinka, O.V.: Topological classification of \[\Omega\] Ω-stable flows on surfaces by means of effectively distinguishable multigraphs. Discret. Contin. Dyn. Syst. 38(9), 4305-4327 (2018b). https://doi.org/10.3934/dcds.2018188 · Zbl 1396.37054 · doi:10.3934/dcds.2018188
[14] Leontovich, E.A., Mayer, A.G.: About trajectories determining qualitative structure of sphere partition into trajectories. Doklady Akademii Nauk SSSR 14(5), 251-257 (1937). (in Russian) · Zbl 0016.11302
[15] Leontovich, E.A., Mayer, A.G.: About scheme determining topological structure of partition into trajectories. Doklady Akademii Nauk SSSR 103(4), 557-560 (1955). (in Russian) · Zbl 0064.33903
[16] Luks, E.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25, 42-65 (1982) · Zbl 0493.68064 · doi:10.1016/0022-0000(82)90009-5
[17] Miller, G.: Isomorphism testing for graphs of bounded genus. In: Proceeding of the 12th Annual ACM Symposium on Theory of Computing, pp. 225-235 (1980)
[18] Oshemkov, A.A., Sharko, V.V.: Classification of Morse-Smale flows on two-dimensional manifolds. Sb. Math. 189(8), 1205-1250 (1998). https://doi.org/10.1070/SM1998v189n08ABEH000341 · Zbl 0915.58045 · doi:10.1070/SM1998v189n08ABEH000341
[19] Palis, J., De Melo, W.: Geometric Theory of Dynamical Systems: An Introduction. Translation from the Portuguese by Manning AK. Springer, New York (1982) · Zbl 0491.58001 · doi:10.1007/978-1-4612-5703-5
[20] Peixoto, M.M.: On the classification of flows on 2-manifolds. In: Dynamical systems Proceedings of Symposium Held at the University of Bahia, Salvador, Brazil, pp. 389-419 (1973) · Zbl 0299.58011
[21] Pesin, YaB, Yurchenko, A.A.: Some physical models of the reaction – diffusion equation, and coupled map lattices. Russ. Math. Surv. 59(3), 481-513 (2004). https://doi.org/10.1070/RM2004v059n03ABEH000737 · Zbl 1160.37423 · doi:10.1070/RM2004v059n03ABEH000737
[22] Robinson, C.: Dynamical Systems: Stability, Symbolic Dynamics, and Chaos. CRC Press, Boca Raton (1995) · Zbl 0853.58001
[23] Wang, X.: The \[C^*C\]∗-algebras of Morse-Smale flows on two-manifolds. Ergod. Theory Dyn. Syst. 10, 565-597 (1990) · Zbl 0728.58017 · doi:10.1017/S0143385700005757
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.