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

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

        по дисциплине: "Экономика"

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

        Выполнил:

        Проверил:

2018

Содержание

Введение        2

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

1.1. Основные  понятия и определения        3

1.2 Раскраска графа        6

2.Задача раскраски вершин графа        9

2.1 Развернутый пример решения        9

2.2 Составление графиков осмотра        11

2.3 Задача составления расписания        11

2.4. Подсчёт числа остовных деревьев        13

2.5. Раскраска графа на примере предприятия        15

Заключение        17

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

Введение

Актуальность работы. Понятие «граф» связано с понятием «графика», «графический». Действительно, модели графов имеют понятную и простую графическую интерпретацию, которая позволяет им представлять множество объектов, оставаясь в рамках строгих математических моделей. Первая работа теории графов как математической дисциплины просматривается в статье Эйлера (1736), в которой рассматривалась проблема мостов Кенигсберга. Эйлер показал, что вы не можете обойти семь городских мостов и вернуться в исходную точку, проходя через каждый мост ровно один раз. Следующий импульс был приведен теории графов почти 100 лет спустя с развитием исследований кристаллографии, электрических сетей, органической химии и других наук. Не замечая того, что с графами, мы сталкиваемся все время. Например, графом представляет собой диаграмму линий метро. Точками на нем являются станции, а линии - дорожки. Рассматривая его родословную и поднимая ее до далекого предка, мы строим так называемое генеалогическое дерево. И это дерево является графом. Методы теории графов широко используются в дискретной математике. Без них невозможно обойтись без синтеза и анализа различных дискретных преобразователей: функциональных блоков компьютеров, программных комплексов и т. д. Теперь теория графов охватывает много материала и развивается активно.

Объект исследования: графы и их расписание.

Предмет исследования: особенности расписания графов.

Цель работы: рассмотреть правильная раскраску графов и оптимальное расписание.

Для осуществления поставленной цели необходимо решить задачи:

- проанализировать основные понятия и определения;

- рассмотреть особенности графов;

- привести задачи примеров раскраски графов и их решение.

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

1.1. Основные  понятия и определения

Граф, или неориентированный граф G — это некоторая пара G=G(V,E), для которой возможны такие  условия:

1. E — это совокупность пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами;
2. V — это непустое множество узлов, или вершин.

Рёбра и вершины графа считаются элементами графа, количество вершин в графе [pic 1] — порядком, число рёбер [pic 2] — размером графа. Вершины [pic 3] и [pic 4] считаются просто концами (или концевыми вершинами) ребра [pic 5]. Ребро также, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними. Два ребра считаются смежными, если имеют они общую концевую вершину.

Если концы ребра совпадают, то называется петлёй, то есть [pic 6] Степень вершины – это количество ребер, входящих в эту вершину. Вершина считается висячей, если ее степень равносильна единице.