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

Введение 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 лет спустя с развитием исследований кристаллографии, электрических сетей, органической химии и других наук. Не замечая того, что с графами, мы сталкиваемся все время. Например, графом представ ляет собой диаграмму линий метро. Точками на нем являются станции, а линии - дорожки. Рассматривая его родословную и поднимая ее до далекого предка, мы строим так называемое генеалогическое дерево. И это дерево является графом. Методы теории графов широко используются в дискретной математике. Без них невозможно обойтись без синтеза и анализа различных дискретных преобразователей: функциональных блоков компьютеров, программных комплексов и т. д. Теперь теория графов охватывает много материала и развивается активно

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