Правильная раскраска графов и оптимальное расписание

 

 

 

 

 

 

 

Курсовая работа

по дисциплине: «Методы моделирования экономики»

на тему: «Правильная раскраска графов и оптимальное расписание»

 

    Выполнила: студентка

                                                                            группы

                                                                            Котова Катя

                                                                            Проверил:

                                                                            ст. преподаватель

                                                        Иванов Б.П.

 

Москва

2013

Теоретическая часть

Произвольное отображение f: V(G)→{1,2,…,k} называется вершинной k-раскраской графа G.

Раскраска называется правильной, если для любых смежных вершин u,vV(G)  f(u)≠f(v), т.е. никакие смежные вершины не окрашены в один цвет.

Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G).

Пример правильной раскраски  графа G:

χ(G)=3

 

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

В компанию N поступил заказ на выполнение объёмного проекта. Проект разбили на 8 составных частей. Каждую часть будем называть заданием. Всего на выполнение проекта выделено 5 сотрудников. Притом каждый сотрудник может выполнить несколько заданий. Ниже приведена матрица выполнения заданий каждым сотрудником.

Таблица 1. Матрица выполнения заданий.

	Задания
	1	2	3	4	5	6	7	8
Андрей				+	+		+
Валерий	+		+		+	+
Дарья	+	+	+				+	+
Евгений		+	+	+			+
Ольга	+				+		+	+

 

Цель: найти минимальное  время, за которое проект будет полностью  завершён.

Математическая постановка задачи: найти хроматическое число  χ, соответствующее количеству недель, необходимому для выполнения всех заданий.

 

 

 

 

Решение задачи

1. Построим граф, где вершины соответствуют номерам заданий. Вершины соединяются рёбрами в том случае, если у заданий под данными номерами есть общий исполнитель-сотрудник.
2. Подсчитаем степени вершин. Отобразим их рядом с соответственными вершинами графа.
3. Начиная с вершины с наибольшей степенью, производим раскраску графа (рис.1):
1. Красным цветом – вершина 5;
2. Оранжевым цветом – вершины 1 и 4;
3. Жёлтым цветом – вершины 7 и 6;
4. Зелёным цветом – вершины 3 и 8;
5. Голубым цветом – вершина 2.

 

6

5

3

7

3

6

4

6

4

3

2

5

6

7

8

1

Рис. 1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таким образом, хроматическое  число χ=5.

Следовательно, осуществление  проекта возможно по истечении минимум 5 недель.

Заключение

 

Целью курсовой работы было нахождение минимального срока, в течение  которого будет завершён проект.

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