Решения прикладных задач теории графов применяются в микроэлектронике, логистике, при проектировании систем высокой доступности и компьютерных сетей. Однако существующие решения имеют недостаточную масштабируемость, вследствие чего применяются только для узких вариаций задач: поиска кратчайшего пути из одной вершины в другую, определения существования такого пути в целом, определения связности отдельной конкретной группы вершин. В работе представлен метод решения нескольких прикладных задач теории графов, основанный на алгебре многомерных матриц. Предлагаемый метод рассмотрен в сравнении с классическими эвристическими методами. Показана возможность получения решения задач, развернутого на все вершины графа и их комбинации, в отличие от заранее выбранных в классическом варианте. Описанный метод, а именно (0, μ)-свернутое произведение матриц, может использоваться для решения задачи поиска пересечения в кликах, определения достижимости вершин в графе и числа комбинаций всех возможных клик в графе, а также для проведения проверки, является ли граф деревом.
1. Мунерман В. И., Мунерман Д. В. О соответствии моделей данных и моделей вычислений // Системы компьютерной математики и их приложения: материалы XXII Междунар. науч. конф. Вып. 22. Смоленск: Изд-во СмолГУ, 2021. С. 146–152. EDN: PVXDHB.
2. Соколов Н. П. Введение в теорию многомерных матриц. Киев: Наукова думка, 1972. 175 с.
3. Левин Н. А., Мунерман В. И. Модели обработки больших объемов данных в системах массового параллелизма // Системы высокой доступности. 2013. Т. 9. № 1. С. 35–43. EDN: PYFMXZ.
4. Мунерман В. И. Архитектура программно-аппаратного комплекса для массовой обработки данных на базе многомерно-матричной модели // Системы высокой доступности. 2015. Т. 11. № 2. С. 13–18. EDN: UBGECV.
5. Захаров В. Н., Мунерман В. И. Параллельный алгоритм умножения многомерных матриц // Современные информационные технологии и ИТ-образование. 2015. Т. 11. № 2. С. 384–390. EDN: WAQFMJ.
6. Морозов С. А., Мунерман В. И., Симаков В. А. Экспериментальный анализ многомерно-матричного подхода к построению маршрутов в графе // Изв. вузов. Электроника. 2022. Т. 27. № 5. С. 676–686. https://doi.org/10.24151/1561-5405-2022-27-5-676-686. – EDN: EXAWHR.
7. Леонов Ю. А. Автоматизация выбора рациональных схем базирования заготовки при синтезе технологических процессов: дис. … канд. техн. наук. Брянск, 2012. 175 с.
8. Петухов А. В., Мельников Д. В., Быстренков В. М. Системы автоматизированного проектирования технологических процессов. Гомель: ГГТУ им. П. О. Сухого, 2011. 143 с.
9. Зыков А. А. Теория конечных графов. Новосибирск: Наука. Сиб. отд-ние, 1969. Т. 1. 542 с.
10. Татт У. Теория графов / пер. с англ. Г. П. Гаврилова. М.: Мир, 1988. 424 с.
11. König D. Gráfok és mátrixok // Matematikai és Fizikai Lapok. 1931. Évf. 38. P. 116–119.
12. Макаров А. И., Мунерман В. И. Использование многомерных матриц для определения параметров графа // Современные информационные технологии и ИТ-образование. 2022. Т. 18. № 3. С. 537–544. https://doi.org/10.25559/SITITO.18.202203.537-544. – EDN: ZZSZDY.
13. Захаров В. Н., Мунерман В. И. Параллельная реализация обработки интенсивно используемых данных на основе алгебры многомерных матриц // Аналитика и управление данными в областях с интенсивным использованием данных (DAMDID/RCDL). Обнинск: ИАТЭ НИЯУ МИФИ, 2015. С. 217–223.
14. Munerman V., Munerman D. An axiomatic approach to the data models formalization for mass data processing // 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). St. Petersburg; Moscow: IEEE, 2020. P. 1996–2000. https://doi.org/10.1109/ EIConRus49466.2020.9039205
15. Малышев А. В. Параллелизация умножения матриц // Электроника и информационные технологии: электрон. журн. 2008. № 2 (4). URL: http://fetmag.mrsu.ru/2008-2/pdf/15_ParallelCalc.pdf (дата обращения: 07.02.2021).
16. Гончаров Е. И. Реализация (λ, µ)-свернутого произведения многомерных матриц средствами операции tensordot из библиотек для тензорной алгебры // Современные информационные технологии и ИТ-образование. 2022. Т. 18. № 4. С. 781–789. https://doi.org/10.25559/SITITO.18.202204.781-789. – EDN: CSWVOH.
17. Choi J., Walker D. W., Dongarra J. J. Pumma: Parallel universal matrix multiplication algorithms on distributed memory concurrent computers // Concurrency: Pract. Exper. 1994. Vol. 6. Iss. 7. P. 543–570. https://doi.org/10.1002/cpe.4330060702
18. Емельченков Е. П., Мунерман В. И., Мунерман Д. В., Самойлова Т. А. Один метод построения циклов в графе // Современные информационные технологии и ИТ-образование. 2021. Т. 17. № 4. С. 814–823. https://doi.org/10.25559/SITITO.17.202104.814-823. – EDN: JOCFXP.
19. Moon J. W., Moser L. On cliques in graphs // Israel J. Math. 1965. Vol. 3. P. 23–28. https://doi.org/ 10.1007/BF02760024
20. Демидова А. А. Автоматный анализ свойств графа быть деревом и псевдодеревом // Интеллектуальные системы. Теория и приложения. 2021. Т. 25. № 2. С. 111–127. EDN: EGAQBJ.