Методы перебора на графе при моделировании сетей передачи данных
Abstract
В статье выделен класс задач моделирования сетей передачи данных, к которым сводятся задачи перечисления на графах, и решение которых возможно с помощью метода перебора. Предложена новая форма задания графа – совокупность узловграфов. Цель – снижение сложности решения задач переборного типа при сохранении универсальности и точности полного перебора. Новая форма представления графа позволила уменьшить размер входных данных задачи и определить как операции, так и специфический регламент трансформации узлаграфа.
Keywords:
модель – model; функционирование – operation; граф – graph; задача перечисления – enumeration problem; перебор – brute force; путь – path, гамильтонов путь – Hamiltonian path.
References
1. Волков, А. С. Разработка алгоритма многопутевой маршрутизации в программно-конфигурируемых сетях связи / А.С. Волков., А.Е. Баскаков // T-Comm: Телекоммуникации и транспорт. – 2021. – Т. 15, № 9. – С. 17–23.
2. Птицын, Г. А. Методы оценки и математические модели живучести сетей связи / Г.А. Птицын // T-Comm: Телекоммуникации и транспорт. – 2016. – Т. 10, № 4. – С. 47–51.
3. Батенков, А. А. Методы формирования множеств состояний телекоммуникационных сетей для различных мер связности / А.А. Батенков, К.А. Батенков, А.Б. Фокин // Труды СПИИРАН. – 2020. – Т. 19, № 3. – С. 644–673.
4. Семенова, И. В. Исследование эффективности моделей прогнозирования нагрузки серверов оператора сотовой связи / И.В. Семенова, Р.Е. Ильдияров // Математическое моделирование. – 2023. – Т. 35, № 1. – С. 83–94.
5. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – Москва : Мир, 1982. – 419 с.
6. Рыбалов, А. Н. О генерической сложности проблемы распознавания гамильтоновых путей / А.Н.Рыбалов // Прикладная дискретная математика. – 2021. – № 53. – С. 120–126.
7. Левин, Л. А. Универсальные задачи перебора / Л.А. Левин // Проблемы передачи информации. – 1973. – Т. 9, Вып. 3. – С. 115–116.
8. Кристофидес, Н. Теория графов Алгоритмический подход / Н. Кристофидес. – Москва : Мир, 1978. – 432 с.
9. Ковшов, А. М. Разделяемый алгоритм перебора разбиений конечного множества на подмножества заданной мощности / А.М. Ковшов // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. – 2020. – Т. 16, № 1. – С. 50–61.
10. Kudelya, V. N. Full enumeration methods on graphs / V.N. Kudelya // T-Comm. – 2023. – Vol. 17, No. 7. – P. 57–64.
11. Куделя, В. Н. Методы перечисления путей в графе / В.Н. Куделя // Наукоемкие технологии в космических исследованиях Земли. – 2023. – Т. 15, № 5. – С. 28–38.
12. Харари, Ф. Перечисление графов / Ф. Харари, Э. Палмер. – Москва : Мир, 1977. – 326 с.
13. Мизин, И. А. Сети коммутации пакетов / И.А. Мизин, В.А. Богатырев, А.П. Кулешов. – Москва: Радио и связь, 1986. – 408 с.