Автор работы: Пользователь скрыл имя, 20 Июня 2014 в 17:41, курсовая работа
Граф называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является r-хроматическим, называется хроматическим числом графа G и обозначается . Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.
Введение 3
1.Теоремы и оценки, относящиеся к хроматическим числам
1.1Нижние оценки для . 5
1.2. Верхние оценки для . 5
1.3. Гипотеза четырех красок. 6
2. Приближенные алгоритмы раскрашивания.
2.1. Переборный алгоритм для раскраски 9
2.2. Раскраска ребер 11
2.3. Рационализация поиска наибольшего независимого множества 15
3. Задачи раскраски.
3.1. Простая задача размещения (загрузки). 17
3.2. Составление графиков осмотра (проверки). 18
3.3. Распределение ресурсов. 18
Заключение 19
Список литературы 21
Или же распределение ресурсов. Пусть для выполнения каких-то n работ надо распределить m имеющихся в наличии ресурсов. Считаем, что каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и что для выполнения i-й работы требуется подмножество ресурсов Si.
Построим граф G: каждой работе соответствует определенная вершина графа, а ребро (xi, xj) существует в графе тогда и только тогда, когда для выполнения i-й и j-й работ требуется хотя бы один общий ресурс, т. е. когда Si∩Sj≠∅. Это означает, что i-я и j-я работы не могут выполняться одновременно. Раскраска графа G определяет тогда некоторое распределение ресурсов (по выполняемым работам), причем такое, что работы, соответствующие вершинам одного цвета, выполняются одновременно. Наилучшее использование ресурсов (т. е. выполнение всех n работ за наименьшее время) достигается при оптимальной раскраске вершин графа G.
Естественно, что круг применения не ограничен приведенными примерами.