АЛГОРИТМЫ СРАВНИТЕЛЬНОГО ИССЛЕДОВАНИЯ ДВУХ ИНВАРИАНТОВ ГРАФА

  • Boris Feliksovich Melnikov Российский государственный социальный университет http://orcid.org/0000-0002-6765-6800
  • Nadezhda Petrovna Churikova Самарский национальный исследовательский университет имени академика С.П. Королева http://orcid.org/0000-0002-6765-6800

Аннотация

Алгоритмы определения изоморфности графов имеют широкое применение в различных областях, таких как: задачи синтаксического и структурного распознавания образов, задачи математической химии, исследование социальных сетей и Интернета, а также соответствующих математических моделей. Кроме того, эти алгоритмы имеют большое значение в теории графов: например, они используются как вспомогательные при вычислении древесной ширины графов. В статье рассмотрены основные существующие подходы к решению проблемы изоморфизма, как точные, так и эвристические. На настоящий момент еще не построен алгоритм, позволяющий решить эту задачу за полиномиальное время, но и доказательств невозможности построения такого алгоритма нет. Работа посвящена исследованию простых связных графов и некоторых быстро вычисляемых инвариантов, а именно: индекса Рандича и вектора степеней второго порядка. Описывается алгоритм создания базы данных, формат данных, программная реализация вычислений и полученные результаты. Приведены результаты сравнения дифференцирующей способности этих инвариантов. Вычисления проводились для всех связных графов с количеством вершин 8, 9 и 10. В качестве программных средств для реализации используются система управления базами данных MongoDB и язык программирования Python 2.7, для создания базы данных использовалась программа nauty, позволяющая получить набор, состоящий из всех связных неизоморфных графов с заданным количеством вершин.

Сведения об авторах

Boris Feliksovich Melnikov, Российский государственный социальный университет

доктор физико-математических наук, профессор, кафедра информационных систем, сетей и безопасности, факультет информационных технологий

Nadezhda Petrovna Churikova, Самарский национальный исследовательский университет имени академика С.П. Королева

аспирант, кафедра информатики и вычислительной математики

Литература

[1] Poddar A., Sahidullah M., Saha G. Speaker verification with short utterances: a review of challenges, trends and opportunities. IET Biometrics. 2018; 7(2):91-101. (In Eng.) DOI: 10.1049/iet-bmt.2017.0065
[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
Опубликована
2019-04-19
Как цитировать
MELNIKOV, Boris Feliksovich; CHURIKOVA, Nadezhda Petrovna. АЛГОРИТМЫ СРАВНИТЕЛЬНОГО ИССЛЕДОВАНИЯ ДВУХ ИНВАРИАНТОВ ГРАФА. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 15, n. 1, p. 45-51, apr. 2019. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/473>. Дата доступа: 15 dec. 2019 doi: https://doi.org/10.25559/SITITO.15.201901.45-51.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук