ALGORITHMS OF COMPARATIVE ANALYSIS OF TWO INVARIANTS OF A GRAPH
Abstract
Algorithms of definition of isomorphism of graphs have wide application in various areas, such as: problems of syntactic and structural recognition of images, problems of mathematical chemistry, research of social networks and the Internet, and also corresponding mathematical models. In addition, these algorithms are of great importance in graph theory: for example, they are used as auxiliary ones in calculating the wood width of graphs. In this paper, we consider the main existing approaches to solving the problem of isomorphism, both full and heuristic ones. At present, there is no algorithm that allows solving this problem in polynomial time, but there is no evidence of the impossibility of constructing such an algorithm. The work is devoted to the study of simple connected graphs and some quickly calculated invariants, namely: the Randić Index and the second-order degree vector. The algorithm of database creation, data format, programmatic implementation of calculations and obtained results are described. The results of comparison of differentiation ability of these invariants are given. Calculations were performed for all connected graphs with the number of vertices 8, 9, and 10. The MongoDB database management system and the Python 3.6 programming language are used as software tools for implementation, and a nauty program was used to create the database, which allows you to get a set consisting of all connected Non-isomorphic graphs with a specified number of vertices. The obtained results allow us to speak about the possibility of their application in the tasks of equivalent conversion of non-deterministic finite machines, construction of effective algorithms for determining the wood width of the graph and some others.
References
[2] Zhang X., Moore C., Newman M. E. J. Random graph models for dynamic networks. The European Physical Journal B. 2017; 90(10):200. (In Eng.) DOI: 10.1140/epjb/e2017-80122-8
[3] Raigorodskii A.M. Small subgraphs in preferential attachment networks. Optimization Letters. 2017; 11(2):249-257. (In Eng.) DOI: 10.1007/s11590-015-0945-9
[4] Bonato A., Pralat P., Raigorodskii A.M. (eds.) Algorithms and Models for the Web Graph. Proceedings of the 15th International Workshop (WAW 2018), Moscow, Russia, May 17-18, 2018. Vol. 10836. Springer International Publishing, 2018. (In Eng.) DOI: 10.1007/978-3-319-92871-5
[5] Melnikov B.F., Sayfullina E.F. Applying multiheuristic approach o randomly generating graphs with a given degree sequence. University proceedings. Volga region. Physical and mathematical sciences. Mathematics. 2013; 3(27):70-83. Available at: https://izvuz_fmn.pnzgu.ru/sf6313 (accessed 18.12.2018). (In Russ.)
[6] Babai L., Erdos P., Selkow S.M. Random Graph Isomorphism. SIAM Journal on Computing. 1980; 9(3):628-635. (In Eng.) DOI: 10.1137/0209047
[7] Melnikova E.A., Sayfullina E.F. Approach to the verification of graph isomorphism by constructing invariants. Vector science Togliatti State University. 2013; 1(23):113-120. Available at: https://elibrary.ru/item.asp?id=20394979 (accessed 18.12.2018). (In Russ.)
[8] Melnikov B.F., Melnikova E.A., Pivneva S.V., Dudnikov V.A., Davydova E.V. Geometric and game approaches for some discrete optimization problems. CEUR Workshop Proceedings. 2018; 2212:312-321. Available at: http://ceur-ws.org/Vol-2212/paper42.pdf (accessed 18.12.2018). (In Eng.)
[9] Melnikov B.F., Sayfullina E.F., Terentyeva Y.Y., Churikova N.P. Application of algorithms for generating random graphs for investigating the reliability of communication networks. Informatization and communication. 2018; 1:71-80. Availible at: https://elibrary.ru/item.asp?id=32651307 (accessed 18.12.2018). (In Russ.)
[10] Chalermsook P., Das S., Even G., Laekhanukit B., Vaz D. Survivable Network Design for Group Connectivity in Low-Treewidth Graphs. arXiv:1802.10403 [cs.DS]. Availible at: https://arxiv.org/abs/1802.10403 (accessed 18.12.2018). (In Eng.)
[11] Chellali M., Haynes T.W., Hedetniemi S.T., Lewis T.M. On ve-degrees and ev-degrees in graphs. Discrete Mathematics. 2017; 340(2):31-38. (In Eng.) DOI: 10.1016/j.disc.2016.07.008
[12] Gera R., Hedetniemi S., Larson C. (eds.) Graph Theory – Favorite Conjectures and Open Problems - 1. Problem Books in Mathematics. Springer, Cham, 2016. (In Eng.) DOI: 10.1007/978-3-319-31940-7
[13] Chartrand G., English S., Zhang P. Kaleidoscopic colorings of graphs. Discussiones Mathematicae Graph Theory. 2017; 37(3):711-727. (In Eng.) DOI: doi.org/10.7151/dmgt.1950
[14] Desormeaux W.J., Haynes T.W., Hedetniemi S.T., Moore C. Distribution centers in graphs. Discrete Applied Mathematics. 2018; 243:186-193. (In Eng.) DOI: 10.1016/j.dam.2018.02.009
[15] Andrews E., Chartrand G., Lumduanhom C., Zhang P. Stars and Their k-Ramsey Numbers. Graphs and Combinatorics. 2017; 33(2):257-274. (In Eng.) DOI: 10.1007/s00373-017-1756-9
[16] Ahangar H.A., Fujie-Okamoto F., Samodivkin V. On the forcing connected geodetic number and the connected geodetic number of a graph. Ars Combinatoria. 2016; 126:323-335. (In Eng.)
[17] Babai L. Graph Isomorphism in Quasipolynomial Time. arXiv:1512.03547 [cs.DS]. Availible at: https://arxiv.org/abs/1512.03547 (accessed 18.12.2018). (In Eng.)
[18] Schmidt D.C., Druffel L.E. A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices. Journal of the ACM. 1976; 23(3):433-445. (In Eng.) DOI: 10.1145/321958.321963
[19] Harary F. Graph Theory. Reading, MA: Addison-Wesley, 1969. (In Eng.)
[20] McKay B.D. Practical graph isomorphism. Congressus Numerantium. 1981; 30:45-87. Availible at: http://users.cecs.anu.edu.au/~bdm/nauty/pgi.pdf (accessed 18.12.2018). (In Eng.)
[21] McKay B.D., Piperno A. Practical graph isomorphism, II. Journal of Symbolic Computation. 2014; 60:94-112. (In Eng.) DOI: 10.1016/j.jsc.2013.09.003
[22] Volodicheva M.I., Leora S.N. Study of graph isomorphism using Jordan forms of adjacency matrices. Prikladnaya Diskretnaya Matematika. 2018; 40:87-90. (In Russ.) DOI: 10.17223/20710410/40/7
[23] Melnikov B.F., Saifullina E.F. Generation of graphs with prespecified sequences of degrees of order two and the isomorphism detection problem. Stohastičeskaâ optimizaciâ v informatike. 2014; 10(2):24-36. Availible at: https://elibrary.ru/item.asp?id=22764354 (accessed 18.12.2018). (In Russ.)
[24] Harary F., Palmer E.M. Graphical Enumeration. New York; London; Oxford; Bosto; San Diego: Academic Press, 2014. (In Eng.)
[25] Churikova N.P. On the differentiation of graphs on the basis of quickly calculated invariants. Proceedings of the "XII Belorussian Mathematical Conference". Vol. 4. Minsk, 2016, pp. 67-69.
[26] Melnikov B.F., Saifullina M.R. Some algorithms for equivalent transformation of nondeterministic finite automata. Russian Mathematics. 2009; 53(4):54-57. (In Eng.) DOI: 10.3103/S1066369X09040100
[27] Melnikov B.F., Melnikova A.A. Edge-minimization of non-deterministic finite automata. Korean Journal of Computational and Applied Mathematics. 2001; 8(3):469-479. (In Eng.) DOI: 10.1007/BF02941980
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
