АЛГОРИТМЫ СРАВНИТЕЛЬНОГО ИССЛЕДОВАНИЯ ДВУХ ИНВАРИАНТОВ ГРАФА
Аннотация
Алгоритмы определения изоморфности графов имеют широкое применение в различных областях, таких как: задачи синтаксического и структурного распознавания образов, задачи математической химии, исследование социальных сетей и Интернета, а также соответствующих математических моделей. Кроме того, эти алгоритмы имеют большое значение в теории графов: например, они используются как вспомогательные при вычислении древесной ширины графов. В статье рассмотрены основные существующие подходы к решению проблемы изоморфизма, как точные, так и эвристические. На настоящий момент еще не построен алгоритм, позволяющий решить эту задачу за полиномиальное время, но и доказательств невозможности построения такого алгоритма нет. Работа посвящена исследованию простых связных графов и некоторых быстро вычисляемых инвариантов, а именно: индекса Рандича и вектора степеней второго порядка. Описывается алгоритм создания базы данных, формат данных, программная реализация вычислений и полученные результаты. Приведены результаты сравнения дифференцирующей способности этих инвариантов. Вычисления проводились для всех связных графов с количеством вершин 8, 9 и 10. В качестве программных средств для реализации используются система управления базами данных MongoDB и язык программирования Python 2.7, для создания базы данных использовалась программа nauty, позволяющая получить набор, состоящий из всех связных неизоморфных графов с заданным количеством вершин.
Литература
[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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
