Задача раскраски графов и ее приложения

Размещено на http://www.allbest.ru/

Министерство сельского хозяйства Российской Федерации

ФГОУ ВПО «Кубанский государственный аграрный университет»

(КубГАУ)

Кафедра компьютерных технологий и систем

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

по дисциплине: «Дискретная математика»

на тему: «Задача раскраски графов и ее приложения»

Студент: Кочеткова Виктория Михайловна

Специальность: Бизнес-информатика

Группа: БИ-1301

Преподаватель: Аршинов Георгий Александрович

Краснодар 2013

Оглавление

Введение

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

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

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

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

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

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

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

Заключение

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

Введение

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

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

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

Граф, или неориентированный граф G -- это упорядоченная пара G=G(V,E) , для которой выполнены следующие условия:

1. V -- это непустое множество вершин, или узлов,

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

Вершины и рёбра графа называются также элементами графа, число вершин в графе -- порядком, число рёбер -- размером графа. Вершины и называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними. Два ребра называются смежными, если они имеют общую концевую вершину.

Ребро называется петлёй, если его концы совпадают, то есть Степень вершины - это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.

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

Рисунок 1

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

Пусть G = (V,E) - некоторый граф. Пусть {1,2,…,k} - множество «цветов». Отображение f : V -- > {1,2,…,k} называют k-раскраской вершин графа G. Такую k-раскраску называют правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается .

Задача раскраски графа считается классической в информатике. Созданные алгоритмы применяются для выдачи радиочастот, составления расписаний и других задач на распределение ресурсов.

К сожалению, не существует оптимального алгоритма. Задачу можно решить либо полным перебором, либо с приближенным значением.

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

1. Неявный перебор;

2. Эвристический метод.

Неявный перебор

Назначим каждой вершине свой номер (xi -- i-я вершина). Получаем первоначальную раскраску:

1) Окрасить xi в цвет 1.

2) Каждую из оставшихся вершин окрашивать последовательно: вершина xi окрашивается в цвет с наименьшим возможным «номером» (т. е. выбираемый цвет должен быть первым в данном упорядочении цветом, не использованным при окраске какой-либо вершины, инцидентной xi). Далее улучшаем раскраску. Отыскиваем первую по номеру вершину с максимальным цветом. Из неё делаем шаг возвращения.

Первая фаза:

1. Находим смежную вершину с максимальным номером, который меньше, чем у нее.

2. Пытаемся перекрасить её в цвет больший собственного, но меньший, чем максимальный цвет в графе.

3. Если это не удается, то делаешь шаг возвращения из этой вершины.

4. Если это удаётся, то по правилу первой фазы перекрашиваем вершины с большим номером.

5. Если при перекрашивании какая-то вершина затребовала максимальный цвет, от которого мы пытаемся избавиться, то делаем шаг возвращения из неё.

6. Если достигнута первая вершина, то завершаем работу.

Вторая фаза - улучшение раскраски:

1. Находим смежную вершину с максимальным номером, который меньше, чем у нее.

2. Пытаемся перекрасить её в цвет больший собственного, но меньший, чем максимальный цвет в графе.

3. Если это не удается, то делаешь шаг возвращения из этой вершины.

4. Если это удаётся, то по правилу первой фазы перекрашиваем вершины с большим номером.

5. Если при перекрашивании какая-то вершина затребовала максимальный цвет, от которого мы пытаемся избавиться, то делаем шаг возвращения из неё.

6. Если достигнута первая вершина, то завершаем работу.

Эвристический метод

Вначале выбираем первый цвет.

1. Сортируем вершины по количеству неокрашенных смежных вершин.

2. Последовательно окрашиваем вершины в выбранный цвет. Если у вершины уже есть смежная вершина с выбранным цветом, то оставляем ее неокрашенной.

3. Если остались неокрашенные вершины, то выбираем следующий цвет и переходим к пункту 1.

Теоретическое обоснование

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

Эвристический метод дает приемлемый результат, поскольку вначале окрашивает вершины с максимальной степенью.

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

В качестве примера возьмём граф, представленный на рисунке 2:

Рисунок 2

Цвета обозначим:

красный: 1,

зеленый: 2,

синий: 3.

Неявный перебор

1. Раскрашиваем вершины по порядку в минимально возможные цвета: 1 -красный, 2 - зеленый, 3 - зеленый, 4 - красный, 5 - синий.

2. Вершина номер 5 имеет максимальный цвет (с номером 3). Попытаемся от него избавиться: делаем шаг возвращения из вершины 5.

3. Смежная вершина с максимальным номером, которая меньше 5 - это 3. Перекрасить ее в цвет больший ее (2) и меньший, чем максимальный (3) - нельзя. Делаем шаг возвращения из вершины 3.

4. Смежная вершина с максимальным номером, которая меньше 3 - это 1. Мы достигли первой вершины и завершаем алгоритм.

Эвристический метод

1. Сортируем вершины по степени: 1, 3, 2, 4, 5.

2. Окрашиваем в первый цвет (красный). Мы можем окрасить вершины 1. Вершины 2 и 3 окрасить нельзя, поскольку они смежные с 1. Вершина 4 не

инцидентна, так что может быть окрашена в красный. Смежную с первой вершину 5 окрасить нельзя.

3. Сортируем вершины по количеству смежных неокрашенных вершин: 3, 2, 5.

4. Выбираем следующий цвет - зеленый. Мы можем окрасить в него вершины 2 и 3.

5. Сортируем вершины по количеству смежных неокрашенных вершин: остаётся только 5.

6. Выбираем следующий цвет - синий (3).

7. Окрашиваем последнюю вершину 5 в синий цвет.

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

Задача о раскраске вершин графа, как было приведено выше, заключается в том, чтобы раскрасить вершины графа так, чтобы любые две смежные вершины были раскрашены в разные цвета, при этом число использованных цветов должно быть наименьшим.

Но задача раскраски в том «чистом» виде, в каком она рассматривается в теории, редко применяется в жизни. Ниже приведены некоторые примеры раскраски, часто встречающиеся на практике. Естественно, что данный список этими примерами не ограничивается.

2.1 Составление графиков осмотра (проверки)

В задачах теории расписаний осмотры представляются, в виде временных интервалов. Каждому осмотру можно сопоставить вершину некоторого графа, причем две любые вершины графа будут соединены ребром лишь тогда, когда соответствующие им осмотры нельзя осуществлять одновременно. Требуется составить такой график осмотра, который связан с наименьшими временными затратами (с учетом приведенных выше ограничений на «совместимость» осмотров). Эта задача эквивалентна задаче о раскраске вершин графа с использованием наименьшего числа цветов. Хроматическое число графа как раз и соответствует осмотру, требующему наименьших временных затрат.

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

Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (например, их читает один и тот же лектор). Построим граф G, вершины которого соответствуют лекциям, и две вершины смежны тогда и только тогда, когда соответствующие лекции нельзя читать одновременно. Очевидно, что любая правильная раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам графа, составляющим цветной класс, читаются одновременно. И, обратно, любое допустимое расписание определяет правильную раскраску графа G. Оптимальные расписания соответствуют минимальным раскраскам, а число часов, необходимое для прочтения всех лекций, равно.

граф алгоритм раскраска вершина

Заключение

В настоящей курсовой работе рассмотрены математические графы, области их применения. Представлены способы раскраски вершин и задачи на их применение. Графы достаточно широко применяются в математике, технике, экономике, управлении. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты).

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

1. Поздняков С.Н. Дискретная математика: учебник для студ. вузов/ С.Н. Поздняков, С.В. Рыбин. - М. : Издательский центр «Академия», 2008. - 448с.

2. Белоусов А.И., Ткачев С.Б. Дискретная математика: учебник для вузов/ Под ред. В.С. Зарубина, А.П. Крищенко. - 3-к изд., стереотип.- М.: Изд-во МГТУ им.

3. Берж К. "Теория графов и ее применение", М., ИЛ, 1962;

4. Носов. В.А. Комбинаторика и теория графов: учебное пособие. - М.: Изд-во МИЭМ( Технический университет),Москва,1999- 166с.

Размещено на Allbest.ru