Использование многомерных матриц для определения параметров графа
Аннотация
При увеличении сложности проектируемых вычислительных систем и компьютерных сетей растет необходимость в определении наиболее подходящей модели данных. Одной из основных моделей для подобного рода задач является графовая модель. Однако для систем с большим числом узлов графы получаются настолько сложными, что эвристические методы, являющиеся основными в теории графов, становятся слишком ресурсозатратными. Но при использовании методов теории многомерных матриц возможно определение отдельных свойств графов, а также их параметров при значительно меньших занимаемых ресурсах вычислительных мощностей. В данной статье рассмотрены некоторые свойства графов, которые возможно проанализировать с использованием (λ,μ)-свернутого произведения многомерных матриц. Проведены доказательства соответствия одного из численных параметров вершин графа и результата возведения матрицы смежности графа в квадрат. Сформулированы параметры графа, не влияющие на его хроматическое число, и выдвинуто предположение о возможной связи между хроматическим числом и числом нечетных циклов в графе.
Литература
2. Munerman V.I., Munerman D.V. About the correspondence of data models and calculation models. Computer Mathematics Systems and Their Applications. 2021;(22):146-152. Available at: https://www.elibrary.ru/item.asp?id=46649891 (accessed 14.06.2022). (In Russ., abstract in Eng.)
3. Munerman V.I. Construction of hardware-software complexes architecture to improve massively data processing. Highly Available Systems. 2015;11(2):13-18. Available at: https://www.elibrary.ru/item.asp?id=23819273 (accessed 14.06.2022). (In Russ., abstract in Eng.)
4. Alam K.S., Shishir T.A., Azharul Hasan K.M. Efficient Partitioning Algorithm for Parallel Multidimensional Matrix Operations by Linearization. In: Senjyu T., Mahalle P.N., Perumal T., Joshi A. (eds.). Information and Communication Technology for Intelligent Systems. ICTIS 2020. Smart Innovation, Systems and Technologies. Vol. 195. Singapore: Springer; 2021. p. 141-149. doi: https://doi. org/10.1007/978-981-15-7078-0_13
5. Chen Y., Li K., Yang W., Xiao G., Xie X., Li T. Performance-Aware Model for Sparse Matrix-Matrix Multiplication on the Sunway TaihuLight Supercomputer. IEEE Transactions on Parallel and Distributed Systems. 2019;30(4):923-938. doi: https://doi. org/10.1109/TPDS.2018.2871189
6. Kwasniewski G., Kabić M., Besta M., VandeVondele J., Solcà R., Hoefler T. Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC'19). New York, NY, USA: Association for Computing Machinery; 2019. Article number: 24. p. 1-22. doi: https://doi.org/10.1145/3295500.3356181
7. Munerman V.I., Usachev V.V. [One way of parallel implementation of matrix multiplication]. Computer Mathematics Systems and Their Applications. 2013;(14):96-98. Available at: https://www.elibrary.ru/item.asp?id=20588350 (accessed 14.06.2022). (In Russ.)
8. Munerman V.I., Samoylova T.A. Parallel implementation for solving optimization problems by means of databases. Highly Available Systems. 2015;11(1):18-22. Available at: https://www.elibrary.ru/item.asp?id=23417734 (accessed 14.06.2022). (In Russ., abstract in Eng.)
9. Munerman V.I., Usachev V.V. [Parallel implementation of matrix multiplication using cloud computing in WINDOWS AZURE]. Computer Mathematics Systems and Their Applications. 2014;(15):97-98. Available at: https://www.elibrary.ru/item.asp?id=21947784 (accessed 14.06.2022). (In Russ.)
10. Munerman V.I., Zakharov V.N. [Parallel Algorithm for Multidimensional Matrix Multiplication]. Modern Information Technologies and IT-Education. 2015;11(2):384-390. Available at: https://www.elibrary.ru/item.asp?id=26167519 (accessed 14.06.2022). (In Russ.)
11. Munerman V.I., Samoylova T.A. Algebraic approach to algorithmization of routing problems. Highly Available Systems. 2018;14(5):50-56. (In Russ., abstract in Eng.) doi: https://doi.org/10.18127/j20729472-201805-08
12. Morozov S.A., Munerman V.I., Simakov V.A. Experimental analysis of multidimensional matrix approach to constructing routings in a graph. Proceedings of Universities. Electronics. 2022;27(5):676-686. (In Russ., abstract in Eng.) doi: https://doi.org/10.24151/1561-5405-2022-27-5-676-686
13. Kirsch R., Sibley C., Sprangel E. Graph universal cycles: Compression and connections to universal cycles. arXiv:2209.14198. 2022. 25 p. doi: https://doi.org/10.48550/arXiv.2209.14198
14. Xu J., Lu M., Liu K. Anti-Ramsey problems for cycles. Applied Mathematics and Computation. 2021;408:126345. doi: https://doi.org/10.1016/j.amc.2021.126345
15. Khoufi I., Laouiti A., Adjih C. A Survey of Recent Extended Variants of the Traveling Salesman and Vehicle Routing Problems for Unmanned Aerial Vehicles. Drones. 2019;3(3):66. doi: https://doi.org/10.3390/drones3030066
16. Hu Y., Yao Y., Lee W.S. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowledge-Based Systems. 2020;204:106244. doi: https://doi.org/10.1016/j.knosys.2020.106244
17. Xu X., Li J., Zhou M. Bi-Objective Colored Traveling Salesman Problems. IEEE Transactions on Intelligent Transportation Systems. 2022;23(7):6326-6336. doi: https://doi.org/10.1109/TITS.2021.3086625
18. Spivak S.I., Ismagilova A.S., Khamitova I.A. Graph-theoretical method for determining routes of complex chemical reactions. Doklady Physical Chemistry. 2010;434(2):169-171. doi: https://doi.org/10.1134/S0012501610100040
19. Emelchenkov E.P., Munerman V.I. One approach to analysis of high-availability systems. Highly Available Systems. 2018;14(5):36-41. (In Russ., abstract in Eng.) doi: https://doi.org/10.18127/j20729472-201805-05
20. Munerman V.I. [Multidimensional-matrix model of mass data processing]. Highly Available Systems. 2012;8(3):019-022. Available at: https://www.elibrary.ru/item.asp?id=18418156 (accessed 14.06.2022). (In Russ.)
21. Goncharov E.I. Multi-Dimensional Definition of Convolution. Modern Information Technologies and IT-Education. 2021;17(3):541-549. (In Russ., abstract in Eng.) doi: https://doi.org/10.25559/SITITO.17.202103.541-549
22. Moon J.W., Moser L. On cliques in graphs. Israel Journal of Mathematics. 1965;3(1):23-28. doi: https://doi.org/10.1007/BF02760024
23. König D. Graphok és mátrixok. Matematikai és Fizikai Lapok. 1931;38:116-119. Available at: http://real-j.mtak.hu/7307 (accessed 14.06.2022). (In Hungarian)
24. Karpov D.V., Gravin N.V. On Proper Colorings of Hypergraphs. Zapiski Nauchnykh Seminarov POMI. 2011;391(3):79-89. Available at: https://www.elibrary.ru/item.asp?id=17730707 (accessed 14.06.2022). (In Russ., abstract in Eng.)
25. Kupavskii A.B., Raigorodskii A.M. Distance graphs with large chromatic numbers and small clique numbers. Doklady Mathematics. 2012;85(3):394-398. doi: https://doi.org/10.1134/S1064562412030295
Это произведение доступно по лицензии 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.
