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

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

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

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