Основные методы теории графов. Задача раскраски графа в информатике. Составление расписаний и других задач на распределение ресурсов. Алгоритм неявного перебора. Составление графиков осмотра. Задача составления расписания. Способы раскраски вершин.
Понятие «граф» связано с понятием «графический», «графика». Действительно, графовые модели имеют простую и понятную графическую интерпретацию, позволяющую с их помощью образно представить самые разные объекты, в то же время оставаясь в рамках строгих математических моделей. Первой работой теории графов как математической дисциплины считают статью Эйлера (1736г.), в которой рассматривалась задача о Кенигсбергских мостах. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.E - это множество пар (в случае неориентированного графа - неупорядоченных) вершин, называемых ребрами. Вершины и ребра графа называются также элементами графа, число вершин в графе - порядком, число ребер - размером графа. Вершины и называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины. Ребро называется петлей, если его концы совпадают, то есть Степень вершины - это число ребер, входящих в эту вершину.Задача о раскраске состоит в нахождении правильной раскраски данного графа в наименьшее число цветов. Назначим каждой вершине свой номер (xi - i-я вершина). 2) Каждую из оставшихся вершин окрашивать последовательно: вершина xi окрашивается в цвет с наименьшим возможным «номером» (т. е. выбираемый цвет должен быть первым в данном упорядочении цветом, не использованным при окраске какой-либо вершины, инцидентной xi). Отыскиваем первую по номеру вершину с максимальным цветом. Если при перекрашивании какая-то вершина затребовала максимальный цвет, от которого мы пытаемся избавиться, то делаем шаг возвращения из нее.В качестве примера возьмем граф, представленный на рисунке 2: Рисунок 2 Раскрашиваем вершины по порядку в минимально возможные цвета: 1-красный, 2 - зеленый, 3 - зеленый, 4 - красный, 5 - синий. Вершина номер 5 имеет максимальный цвет (с номером 3). Попытаемся от него избавиться: делаем шаг возвращения из вершины 5. Делаем шаг возвращения из вершины 3.Задача о раскраске вершин графа, как было приведено выше, заключается в том, чтобы раскрасить вершины графа так, чтобы любые две смежные вершины были раскрашены в разные цвета, при этом число использованных цветов должно быть наименьшим. В задачах теории расписаний осмотры представляются, в виде временных интервалов. Каждому осмотру можно сопоставить вершину некоторого графа, причем две любые вершины графа будут соединены ребром лишь тогда, когда соответствующие им осмотры нельзя осуществлять одновременно.Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (например, их читает один и тот же лектор). Построим граф G, вершины которого соответствуют лекциям, и две вершины смежны тогда и только тогда, когда соответствующие лекции нельзя читать одновременно.В настоящей курсовой работе рассмотрены математические графы, области их применения.
План
Оглавление
Введение
1. Теоретическая часть
1.1 Основные определения
1.2 Раскраска графа
1.3 Развернутый пример решения
2. Задача раскраски вершин графа
2.1 Составление графиков осмотра
2.2 Задача составления расписания
Заключение
Список литературы
Введение
Понятие «граф» связано с понятием «графический», «графика». Действительно, графовые модели имеют простую и понятную графическую интерпретацию, позволяющую с их помощью образно представить самые разные объекты, в то же время оставаясь в рамках строгих математических моделей. Первой работой теории графов как математической дисциплины считают статью Эйлера (1736г.), в которой рассматривалась задача о Кенигсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам. С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Точками на ней представлены станции, а линиями - пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы стоим так называемое генеалогическое древо. И это древо - граф. Методы теории графов широко применяются в дискретной математике. Без них невозможно обойтись при анализе и синтезе различных дискретных преобразователей: функциональных блоков компьютеров, комплексов программ и т.д. В настоящее время теория графов охватывает большой материал и активно развивается.
Вывод
В настоящей курсовой работе рассмотрены математические графы, области их применения. Представлены способы раскраски вершин и задачи на их применение. Графы достаточно широко применяются в математике, технике, экономике, управлении. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты).
Список литературы
1. Поздняков С.Н. Дискретная математика: учебник для студ. вузов/ С.Н. Поздняков, С.В. Рыбин. - М. : Издательский центр «Академия», 2008. - 448с.
2. Белоусов А.И., Ткачев С.Б. Дискретная математика: учебник для вузов/ Под ред. В.С. Зарубина, А.П. Крищенко. - 3-к изд., стереотип.- М.: Изд-во МГТУ им.
3. Берж К. "Теория графов и ее применение", М., ИЛ, 1962;
4. Носов. В.А. Комбинаторика и теория графов: учебное пособие. - М.: Изд-во МИЭМ( Технический университет),Москва,1999- 166с.
Размещено на .ru
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
