Комбинаторный алгоритм нахождения количества путей на ориентированном графе
- Авторы: Ерусалимский Я.М.1, Чердынцева М.И.2
-
Учреждения:
- Южный федеральный университет
- Южный федеральный университета
- Выпуск: Том 204 (2022)
- Страницы: 37-43
- Раздел: Статьи
- URL: https://journals.rcsi.science/2782-4438/article/view/269973
- DOI: https://doi.org/10.36535/0233-6723-2022-204-37-43
- ID: 269973
Цитировать
Полный текст
Аннотация
В работе приведен алгоритм нахождения количества путей на ориентированном графе, начинающихся в произвольном подмножестве его вершин. Алгоритм основан на идеях, лежащих в основе построения треугольника Паскаля. Трудоемкость алгоритма совпадает с трудоемкостью известного алгоритма Дейкстры нахождения кратчайших путей на графах. Также осуществлена адаптация предложенного алгоритма для решения этой задачи на графах с ограничениями на достижимость.
Ключевые слова
Об авторах
Яков Михайлович Ерусалимский
Южный федеральный университет
Автор, ответственный за переписку.
Email: ymerusalimskiy@sfedu.ru
Россия
Марина Игоревна Чердынцева
Южный федеральный университета
Email: micherdynceva@sfedu.ru
Россия
Список литературы
- Басангова Е. О., Ерусалимский Я. М. Различные виды смешанной достижимости// в кн.: Алгебра и дискретная математика. — Элиста: КалмГУ, 1985. — С. 70-75.
- Басангова Е. О., Ерусалимский Я. М. Смешанная достижимость на частично ориентированных графах// в кн.: Вычислительные системы и алгоритмы. — Ростов-на-Дону: РГУ, 1983. — С. 135-140.
- Ерусалимский Я. М. 2-3 paths in a lattice graph. Random walks// Мат. заметки. — 2018. — 104, № 3. — С. 396-406.
- Ерусалимский Я. М. Дискретная математика. Теория и практикум. — СПб.: Лань, 2018.
- Ерусалимский Я. М. Треугольник Паскаля: комбинаторика и случайные блуждания. — М.: Вузовская книга, 2020.
- Ерусалимский Я. М., Петросян А. Г. Многопродуктовые потоки в сетях с нестандартной достижи мостью/ / Изв. вузов. Сев.-Кав. рег. Естеств. науки. Прилож. — 2005. — №6. — С. 8-16.
- Ерусалимский Я. М, Скороходов В. А. Общий подход к нестандартной достижимости на графах// Изв. вузов. Сев.-Кав. рег. Естеств. науки. — 2005. — Спецвыпуск. Псевдодифференциальные уравне ния и некоторые проблемы математической физики. — С. 64-67.
- Ерусалимский Я. М, Скороходов В. А. О потоках в сети с ограничениями на достижимость. Вычисли тельный эксперимент// Мат. Весенней Воронеж. мат. школы «Современные методы теории краевых задач» (Понтрягинские чтения-XXVI). — ВГУ, 2015. — С. 89-90.
- Ерусалимский Я. М, Скороходов В. А. Потоки в сетях со связанными дугами// Изв. вузов. Сев.-Кав. рег. Естеств. науки. Прилож. — 2003. — № 8. — С. 9-12.
- Ерусалимский Я. М, Скороходов В. А. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость// Изв. вузов. Сев.-Кав. рег. Естеств. науки. Прилож. — 2003. — № 8. — С. 3-8.
- Ерусалимский Я. М, Скороходов В. А., Кузьминова М. В., Петросян А. Г. Графы с нестандартной достижимостью. Задачи, приложения. — Ростов-на-Дону: ЮФУ, 2009.
- Жилякова Л. Ю. Графовые динамические модели и их свойства// Автомат. телемех. — 2015. — 8. — С. 115-139.
- Dijkstra E. W. A note on two problems in connexion with graphs// Numer. Math. — 1959. — 1. — P. 269-271.
- Erusalimskiy I. M. Graph-lattice: random walk and combinatorial identities// Bol. Soc. Mat. Mexicana. — 2016. — 22, № 2. — P. 329-335.
Дополнительные файлы
