Комплекс программ оптимального раскрашивания множества вершин связного графа с использованием метода ветвей и границ

363

Аннотация

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

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

Ключевые слова: Теория графов, графы, раскраска графов, метод ветвей и границ

Рубрика издания: Комплексы программ

Тип материала: научная статья

Для цитаты: Нефедов В.Н., Жарких А.В. Комплекс программ оптимального раскрашивания множества вершин связного графа с использованием метода ветвей и границ // Моделирование и анализ данных. 2019. Том 9. № 3. С. 94–98.

Фрагмент статьи

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

Литература

  1. Кристофидес Н. Теория графов. Алгоритмический подход. –М.: Мир, 1978. – 432 с.
  2. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. –М.: Наука, 1975. –360 с.
  3. Липский В. Комбинаторика для программистов. –М.: Мир, 1988. –200
  4. Шкурба В.В. Задача о трёх станках –М.: Наука, 1976. –92 с.
  5. Нефедов В.Н. Методические указания к выполнению расчетных работ по теории гра-фов и сетей. –М.: Доброе слово, 2015. –59 с.
  6. Нефедов В.Н. Дискретные задачи оптимизации: Учебное пособие. – М.: Изд-во МАИ, 1994. –59 с.
  7. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Изд-во МАИ, 1992. –264 с.

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

Нефедов Виктор Николаевич, кандидат физико-математических наук, доцент кафедры математической кибернетики, Московский авиационный институт (национальный исследовательский университет), Москва, Россия, e-mail: nefedovvn54@yandex.ru

Жарких Алексей Владимирович, студент магистратуры факультета информационных технологий и прикладной математики, Московский авиационный институт (национальный исследовательский университет), Москва, Россия, e-mail: alexvzhar@gmail.com

Метрики

Просмотров

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

Скачиваний

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