Тип работы:
Предмет:
Язык работы:


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

Работа №125830

Тип работы

Бакалаврская работа

Предмет

информационные системы

Объем работы30
Год сдачи2017
Стоимость4650 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
29
Не подходит работа?

Узнай цену на написание


Введение 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

Теория графов активно развивается на протяжении последних нескольких десятилетий. Связано это с тем, что стремительно расширяется область приложений теории графов, увеличивается количество задач, которые могут быть решены посредством методов теории графов. Так, например, основополагающей для задач, связанных с навигацией и построением сетей, является задача нахождения кратчайшего пути на графе. Другой актуальной задачей является задача составления расписаний. Задача подразумевает составление абсолютно любого расписания: от школьного расписания до порядка проведения работ на предприятии. Ограничениями в данной задаче является невозможность проведения заданий (уроков, работ и т. п.) одновременно по ряду причин. Подобная задача возникает постоянно в различных ситуациях, поэтому для её решения необходим эффективный алгоритм.
Одной из трудных задач теории графов является задача отыскания хроматического числа графа, то есть минимального числа цветов, необходимых для раскраски вершин графа. Предложены различные алгоритмы решения данной задачи, однако поиск эффективного алгоритма продолжается. Раскраска вершин позволяет моделировать многие проблемы планирования. В частности, при помощи алгоритма раскраски графа может быть решена задача составления расписания.
В рамках данной работы рассматривается сведение задачи составления расписания с ограничениями к задаче о вершинной раскраске графа, осуществляется анализ алгоритма вершинной раскраски графа, предложенный Красновой А. Ю. [1] и предлагается альтернативный алгоритм раскраски графа.
План работы:
1. Задача раскраски графа и рассмотрение существующих алгоритмов её решения.
2. Реализация и анализ алгоритма, предложенного Красновой А. Ю. [1].
3. Разработка алгоритма решения задачи раскраски графа.
4. Сравнение результатов работы алгоритмов, реализованных в пунктах 2 и 3.
5. Сведение задачи составления расписания с ограничениями к задаче раскраски графа и применение разработанного алгоритма к её решению.
В первой главе работы приведены некоторые определения из теории графов, используемые в работе (граф, смежные вершины, матрица смежности), описывается задача раскраски графа, её варианты, а также подходы к нахождению неточного решения: последовательный перебор, жадные алгоритмы и алгоритмы с использованием битовых операций.
Вторая глава описывает схему и реализацию алгоритма, предложенного Красновой А. Ю., и разработанного в рамках данной работы алгоритма. В заключении главы представлено сравнение работы на коллекции DIMACS- файлов.
Третья глава посвящена задаче о составлении расписания. В начале главы приводится постановка задачи в её самом простом случае и вариант усложнения задачи. Далее в главе рассмотрен пошагово способ решения задачи: от исходных данных до результата. В конце главы приводится пример задания на тестовом расписании.
В заключении перечислены результаты работы и приводятся примеры разработок программных продуктов для составления расписания.

Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!


Составление расписаний является неотъемлемой частью повседневной жизни. Зачастую при составлении расписания изначально известно только то, что необходимо сделать и что нельзя сделать одновременно. Оптимально составленное расписание способно принести большую выгоду, но при этом поиск такого расписания может занять длительное время. Для ускорения процесса необходим способ решать данную задачу с использованием современных технологий.
Одним из способов нахождения расписания является сведение этой задачи к важной задаче теории графов - задаче о раскраске графа. Поиск методов эффективного решения последней продолжается и сейчас.
В данной работе проведен анализ алгоритма вершинной раскраски графа, предложенный Красновой А. Ю., предложен новый алгоритм вершинной раскраски графа и проведено сравнение работы рассмотренных алгоритмов раскраски на коллекции графов. Полученный алгоритм раскраски вершин графа был применен к решению задачи составления расписаний и осуществлена программная реализация для демонстрации работоспособности предложенного подхода.


1. Краснова Александра Юрьевна. Матрицы инциденций и раскраски графа: диссертация ... кандидата физико-математических наук: 01.01.09 / Краснова Александра Юрьевна; [Место защиты: С.-Петерб. гос. ун-т]. - Санкт-Петербург, 2009, 87 с.: ил.
2. Глоссарий теории графов на Википедии.
ййр8://ги^1к1ре&а.огц^1к1/Глоссарий теории графов
3. Оре О. Графы и их применение. М.: Мир, 1965, 174 стр.
4. Татт У. Теория графов. М.: Мир, 1988, 424 стр.
5. Харари Ф. Теория графов. М.: Мир, 1973, 300 стр.
6. Раскраска графов на Википедии.
https://ru.wikipedia.org/wiki/Раскраска графов
7. Бацын М. В., Комоско Л. Ф. Быстрый алгоритм для решения задачи о раскраске графа с использованием битовых операций // Труды 38-й конференции «Информационные технологии и системы - 2014» Н. Новгород: ИППИ РАН, 2014. С. 432-438.
8. Coloring Problems. DIMACS Graph Format.
http: //prolland.free.fr/works/research/dsat/dimacs.html
9. Graph Coloring Instances.
http://mat.gsia.cmu.edu/COLOR/instances.html


Работу высылаем на протяжении 30 минут после оплаты.




©2025 Cервис помощи студентам в выполнении работ