Курсовая работа: Раскраска графов и задача построения расписания с ограничениями

Содержание

Введение..................................................................................................................................... 3

Глава 1. Вершинная раскраска графа............................................................................... 5

Глава 2. Реализация алгоритмов раскраски................................................................... 8

2.1. Алгоритм раскраски графа Красновой А. Ю.................................................... 8

2.2. Алгоритм раскраски графа...................................................................................... 9

2.3. Сравнение алгоритмов........................................................................................... 11

Глава 3. Задача о составлении расписания.................................................................. 14

3.1. Постановка задачи................................................................................................... 14

3.2. Решение задачи......................................................................................................... 14

3.3. Пример работы программы.................................................................................. 17

Заключение.............................................................................................................................. 20

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

Приложение............................................................................................................................ 22

Приложение 1.................................................................................................................... 22

Приложение 2.................................................................................................................... 25

Введение


Теория графов активно развивается на протяжении последних нескольких десятилетий. Связано это с тем, что стремительно расширяется область приложений теории графов, увеличивается количество задач, которые могут быть решены посредством методов теории графов. Так, например, основополагающей для задач, связанных с навигацией и построением сетей, является задача нахождения кратчайшего пути на графе. Другой актуальной задачей является задача составления расписаний. Задача подразумевает составление абсолютно любого расписания: от школьного расписания до порядка проведения работ на предприятии. Ограничениями в данной задаче является невозможность проведения заданий (уроков, работ и т. п.) одновременно по ряду причин. Подобная задача возникает постоянно в различных ситуациях, поэтому для её решения необходим эффективный алгоритм.

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

рамках данной работы рассматривается сведение