Методы перебора на графе при моделировании сетей передачи данных

Куделя В. Н., Сахарова М. А., Вовк В. В.

Читать статью полностью

  Методы перебора на графе при моделировании сетей передачи данных(1,97 MB)

Аннотация

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

Ключевые слова:

модель – model; функционирование – operation; граф – graph; задача перечисления – enumeration problem; перебор – brute force; путь – path, гамильтонов путь – Hamiltonian path.

Список литературы

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 с.