Перейти к основному содержанию

Моделирование и анализ данных
2021. Том 11. № 1. С. 33–39
doi:10.17759/mda.2021110103
ISSN: 2219-3758 / 2311-9454 (online)

Алгоритм покрытия вершин ориентированного графа

81

Князятов М.О., Рассказова В.А.

PDF (RUS)
GS
Информация
в Google Scholar

Аннотация

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

Общая информация

Ключевые слова: покрытие вершин графа, перемещение локомотивов, множество путей

Рубрика издания: Методы оптимизации

DOI: https://doi.org/10.17759/mda.2021110103

Для цитаты: Князятов М.О., Рассказова В.А. Алгоритм покрытия вершин ориентированного графа // Моделирование и анализ данных. 2021. Том 11. № 1. С. 33–39. DOI: 10.17759/mda.2021110103

Литература

  1. Лазарев А.А. Оценки абсолютной погрешности и схема приближенного решения задач теории расписаний // Журнал вычислительной математики и математической физики. 2009.Т. 49. № 2. C. 14–34.
  2. Гафаров Е.Р., Лазарев А.А. Преобразование сетевого графика задач теории расписаний с ограничениями предшествования // ДАН. 2008. Т. 424. № 2. C. 7–9.
  3. Burdett O., Kozan E. A Disjunctive Graph Model and Framework for Constructing New Train Schedules // Eur. J. Oper. Res. 2010. V. 200. P. 85–98.
  4. Gholami O., Sotskov Y.N. Mixed Graph Model and Algorithms for Parallel Machine Job shop Scheduling Problems // Int. J. Production Research. 2015. V. 8. P. 1–16.
  5. Lusby R., Ryan D. Railway Track Allocation: Models and Methods // Oper. Res. Spektrum. 2011. V. 33. P. 843–883.
  6. Гайнанов Д.Н., Рассказова В.А. Математическое моделирование в задаче оптимального назначения и перемещения локомотивов методами теории графов и комбинаторной оптимизации // Труды МАИ. 2017. № 92.
  7. Осипов С.И, Осипов С.С. Основы тяги поездов. М.: УМК МПС, 2000, 592 С.
  8. Гайнанов Д. Н. Комбинаторная геометрия и графы в анализе несовместных систем и распознавании образов. М.: Наука, 2014, 152 С.
  9. Гайнанов Д.Н., Кибзун А.И., Рассказова В.А. Теоретико-графовый алгоритм решения задачи о назначении и перемещении локомотивов // Вестник компьютерных и информационных технологий. 2017. № 5. С. 51–56.
  10. Гайнанов Д.Н., Рассказова В.А. Алгоритм расшифровки монотонных булевых функций, порожденных неориентированными графами // Вестник ЮРГУ. 2016. Т. 9. № 3. С. 17–30.

Информация об авторах

Князятов Михаил Олегович, Студент, Московский авиационный институт (МАИ), Москва, Россия, ORCID: https://orcid.org/0000-0002-2346-4364, e-mail: mike-99@bk.ru

Рассказова Варвара Андреевна, кандидат физико-математических наук, доцент кафедры 804 «Теория вероятностей и компьютерное моделирование», Московский авиационный институт (НИУ МАИ), Москва, Россия, ORCID: https://orcid.org/0000-0003-4943-3133, e-mail: varvara.rasskazova@mail.ru

Метрики

Просмотров

Всего: 272
В прошлом месяце: 6
В текущем месяце: 1

Скачиваний

Всего: 81
В прошлом месяце: 0
В текущем месяце: 0