Р.А. Кочкаров1, А.В. Тимошенко2, А.М. Казанцев3, А.М. Кочкаров4, А.А. Омельшин5

1–3 Финансовый университет при Правительстве Российской Федерации (Москва, Россия)
4 Северо-Кавказская государственная академия (г. Черкесск, Россия)
5 Военный университет радиоэлектроники (г. Череповец, Россия)
1 rkochkarov@fa.ru

Постановка проблемы. Обеспечение структурно-функциональной устойчивости и целостности пространственно-распреде­ленных информационных систем мониторинга в условиях воздействия дестабилизирующих факторов требует проведения процедур оптимизации, математическую основу которых составляет в том числе решение NP-полных задач. Актуальность проблемы обусловлена ограниченной применимостью известных методов дискретной оптимизации для пространственно-распределенных систем большой размерности, моделируемых на основе предфрактальных графов.

Цель. Разработка методики исследования NP-полных задач для пространственно-распределенных информационных систем мониторинга большой размерности на основе адаптации классических NP-полных задач на больших предфрактальных графах.

Результаты. Предложен метод решения частных постановок NP-полных задач на больших предфрактальных графах, учитывающая свойства самоподобия и иерархической структуры предфрактальных графов и включающая в себя последовательные этапы разбиения задачи на иерархические подзадачи, рекурсивного решения этих подзадач и построения на их основе глобального решения.

Практическая значимость. Предложенная методика позволяет снижать вычислительную сложность при решении оптимизационных постановок NP-полных задач на больших графах, что обуславливает применимость для обеспечения структурно-функциональной устойчивости и целостности пространственно-распределенных информационных систем мониторинга в условиях воздействия дестабилизирующих факторов.

Кочкаров Р.А., Тимошенко А.В., Казанцев А.М., Кочкаров А.М., Омельшин А.А. Решение NP-полных задач обеспечения структурно-функциональной устойчивости пространственно-распределенных информационных систем мониторинга // Динамика сложных систем. 2025. Т. 19. № 5. С. 57−68. DOI: 10.18127/j19997493-202505-07

1. Кочкаров Р.А., Чиров Д.С., Тимошенко А.В., Казанцев А.М. Модель пространственно-распределенной информационной системы непрерывного мониторинга с предфрактальной динамической структурой в условиях воздействия дестабилизирующих факторов // T-Comm: Телекоммуникации и транспорт. 2025. Т. 19. № 1. С. 4–12. DOI 10.36724/2072-8735-2025-19-1-4-12
2. Кочкаров Р.А., Балдычев М.Т., Казанцев А.М. и др. Алгоритм оценки структурно-функциональной устойчивости и целостности гетерогенной сети передачи данных пространственно-распределенной системы мониторинга // Труды МАИ. 2024. № 137.
3. Шевцов В.А., Казанцев А.М., Тимошенко А.В. и др. Показатель структурной эффективности управления информационным взаимодействием в гетерогенной сети передачи данных пространственно-распределенной системы мониторинга // Вестник Воронежского государственного технического университета. 2024. Т. 20. № 2. С. 124–131. DOI 10.36622/1729-6501.2024. 20.2.019
4. Кочкаров Р.А., Кочкаров А.А. Теоретико-графовый алгоритм динамического назначения средств системы непрерывного мониторинга // Успехи современной радиоэлектроники. 2023. Т. 77. № 9. С. 44–50. DOI 10.18127/j20700784-202309-05
5. Kirkpatrick S., Gelatt C.D. & Vecchi M.P. Optimization by Simulated Annealing. Science. 1983. № 220(4598). P. 671–680.
6. Sörensen K. Metaheuristics for the Vehicle Routing Problem: A Review. Transportation Science. 2015. № 49 (3). P. 637–657.
7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: пер. с англ. М.: Мир. 1982. 416 с.
8. Харари Ф. Теория графов: пер. с англ. М.: Мир. 1973. 301 с.
9. Karci A. Efficiency and Inefficiency Assessment of Graph Nodes for NP-Complete Problems.
10. Huh J.-H., Hwa J. & Seo Y.-S. Hierarchical System Decomposition Using Genetic Algorithm for Future Sustainable Computing. Sustainability. 2020. № 12 (6). P. 2177–2209. DOI: 10.3390/su12062177 MDPI
11. Hertz A. Polynomially solvable classes for the maximum stable set problem. Discrete Applied Mathematics. 1995. № 60. P. 195–210. DOI: 10.1016/0166-218X(94)00051-E
12. Hertz A. On the use of boolean methods for the computation of the stability number. Discrete Applied Mathematics. 1997. № 76.
    P. 183–203. DOI: 10.1016/S0166-218X(96)00124-2
13. Golumbic M.C. Algorithmic graph theory and perfect graphs. New-York: Academic Press. 1980. 284 p. DOI: 10.1016/C2013-0-10739-8
14. Grotschel M., Lovasz L., Schrijver A. Polynomial algorithms for perfect graphs. Annals of Discrete Mathematics. 1984. № 21. P. 325–356. DOI: 10.1016/S0304-0208(08)72943-8
15. Айзерман М.А., Гусев Л.А., Петров С.В., Смирнова И.М., Тененбаум Л.А. Динамический подход к анализу структур, описываемых графами (основы графодинамики). Исследования по теории структур. М.: Наука. 1988. С. 5–76.
16. Иорданский М.А. Конструктивная классификация графов // Моделирование и анализ информационных систем. 2012. № 19 (4). C. 144–153. DOI: 10.18255/1818-1015-2012-4-144-153
17. Макаренко С.И. Модели системы связи в условиях преднамеренных дестабилизирующих воздействий и ведения разведки: монография. СПб.: Наукоемкие технологии. 2020. 337 с.
18. Тимошенко А.В., Кочкаров Р.А., Кочкаров А.А. Выделение условий разрешимости NP-полных задач для класса предфрактальных графов // Моделирование и анализ информационных систем. 2021. Т. 28. № 2. С. 126–135. DOI: 10.18255/1818-1015-2021-2-126-135
19. Кочкаров Р.А. Задачи многокритериальной оптимизации на много-взвешенных предфрактальных графах. М.: Академинновация. 2014. 189 с.
20. Кочкаров А.М. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН САО. 1998. 170 с.
21. Прокофьев B.C., Малышев В.А. Нечеткие алгоритмы планирования распределения ресурсов системы управления военного назначения // Вестник Воронеж. ин-та высок, технол. 2008. № 3. С. 50–53.
22. Aziz F., Akbar M.S., Jawad M., Malik A.H., Uddin M.I., Gkoutos G.V. Graph characterisation using graphlet-based entropies. Pattern Recognition Letters. 2021. № 147. P. 100–107. DOI: 10.1016/j.patrec.2021.03.031
23. Aziz F., Ullah A., Shah F. Feature selection and learning for graphlet kernel. Pattern Recognition Letters. 2020. № 136. P. 63–70. DOI: 10.1016/j.patrec.2020.05.023
24. Касьянов В.Н., Касьянова Е.В. Модель атрибутированных иерархических графов с портами для визуализации сложно структурированной информации / Сб. науч. тр. XXI открытой Всерос. конф. «Преподавание информационных технологий в Российской Федерации». Нижний Новгород, 18–19 мая 2023 г. Нижний Новгород: Издательство Нижегородского государственного университета им. Н.И. Лобачевского. 2023. С. 53–54.
25. Кочкаров А.А., Калашников Н.В., Кочкаров Р.А. Сравнительный анализ алгоритмов выявления сообществ в сложных сетевых системах на примере социальных сетей // Программные продукты и системы. 2020. № 2. С. 349–356. DOI: 10.15827/ 0236-235X.130.349-356
26. Pisinger D. & Ropke S. A General Variable Neighborhood Search Heuristic for the Periodic Vehicle Routing Problem. Computers & Operations Research. 2007. № 34 (11). P. 3252–3268.
27. Сирота А.А. Компьютерное моделирование и оценка эффективности сложных систем. М.: Техносфера. 2006. 280 с.
28. Ахо А.В., Хопкрофт Д.Э. и др. Структуры данных и алгоритмы. М.: Вильямс. 2007. 400 с.
29. Moreno L.Q. Graphlets and Motifs in Biological Networks. Encyclopedia of Bioinformatics and Computational Biology. 2019. № 2. P. 814–820. DOI: 10.1016/B978-0-12-809633-8.20291-4
30. Алексеев В.Е. Исследование количественных и сложностных характеристик наследственных классов графов: автореферат дисс. ... доктора физико-математических наук: 01.01.09. Нижний Новгород: Нижегор. гос. ун-т им. Н. И. Лобачевского. 2002. 14 с.
31. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход. М.: ФИЗМАТЛИТ. 2002. 144 с.
32. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Высшая школа. 1982. 256 с.
33. Малинецкий Г.Г., Кочкаров А.А., Кочкаров Р.А. Некоторые аспекты динамической теории графов // Журнал вычислительной математики и математической физики. 2015. Т. 55. № 9. С. 1623–1629. DOI: 10.7868/S0044466915090094
34. Дорожко И.В., Осипов Н.А. Методика синтеза оптимальных стратегий диагностирования автоматизированных систем управления сложными техническими объектами с использованием априорной информации // Труды СПИИРАН. 2012.
    № 1(20). С. 165–185.
35. Кочкаров А.А., Салпагаров М.Б., Кочкаров Р.А. Моделирование разрушения сложных систем с ациклической структурой // Управление большими системами: сб. тр. 2007. № 17. С. 103–120.
36. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир. 1966. 276 с.