Алгоритм раскраски графа

Алгоритм раскраски графа

Министерство образования и науки

Государственное образовательное учреждение

высшего профессионального образования

«Сибирский государственный индустриальный университет»

Кафедра информационных технологий в металлургии

Курсовая работа: «Алгоритм раскраски графа»

Выполнил: студент гр. ИСТ-М-12

О.А. Маломыжева

Проверил: ктн, доцент

С.Ю. Красноперов

Новокузнецк 2013г.

Введение

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

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

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

Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами). Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, также называются смежными (или соседними). Граф определяется как совокупность множества М с заданным на нем бинарным отношениемТМ2 .

Между элементами М и Т определено отношение инцидентности, т.е. связи между двумя элементами множества М через один элемент множества Т, представлено на рисунке 1.

Рисунок 1 - Пример графа «звезда»

Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой). Помимо этого, в теории графов рассматриваются также мультиграфы - это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами. Маршрут в графе - это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней. Путь в графе (иногда говорят простой путь) - это маршрут без повторения вершин (а значит, и ребер). Контур - это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней. Последовательности вершин (рис. 2): 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 - это контур.

Рисунок 2 - «Неправильный» граф

Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j - обратной дугой (или обратным ребром). Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). На рис. 2 изображен связный граф. Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком. Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов). Степень вершины - это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.

Лемма 1. Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.

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

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

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

Сложность полного перебора равна O(nn) , где n - это количество вершин. В реальной ситуации сложность, конечно, будет меньше - O(4n) или O(5n) , поскольку большинство вводимых человеком графов скорее будут планарными, либо иметь малое количество пересечений.

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

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

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

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

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

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

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

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

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

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

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

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

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

Далее улучшаем раскраску. Отыскиваем первую по номеру вершину с максимальным цветом. Из неё делаем шаг возвращения:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.2 Раскраска графа

Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета - это числа . Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве . Раскраску можно также рассматривать как разбиение множества вершин , где  - множество вершин цвета . Множества  называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа  в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается .

Пример:

Правильная раскраска графа G может выглядеть следующим образом:

Рисунок 3- Пример раскраски графа

Функцией Гранди называется функция на вершинах графа, отображающая вершины в множество {1,2,…, a}, причем если вершина xi окрашена в цвет с номером k, то функция Гранди h(xi) = k. Ясно, что для данного графа хроматическое число является единственным, но функций Гранди может быть очень много. Естественно, что найти хотя бы одну функцию Гранди - это значит, найти одну из возможных “наилучших” раскрасок (таких раскрасок может быть много). Заметим, что если данный граф является полным, т. е. любые две вершины являются смежными, то хроматическое число такого графа равно п, где п - число вершин.

.4 Тестовый пример

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

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

красный: 1,

зеленый: 2,

синий: 3.

Рисунок 4 - Пример графа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача: разработка программы, которая бы обеспечила ввод графа и его раскраску. Раскраска графа - присвоение каждой вершине графа значения (цвета), так чтобы вершины с одинаковым значением не были инцидентны. Количество используемых значений должно быть минимально.

Программа должна быть удобной в использовании. Ввод графа должен осуществляться через графический интерфейс. Должна быть предусмотрена правка структуры графа на любом этапе работы с программой. Рассматриваемый граф неориентированный и не имеет петель.

3. Практическая часть

.1 Разработанный алгоритм

Разработанный алгоритм работает на основе операций с матрицей смежности.

Данный алгоритм реализуется следующим образом:

За основу берется матрица смежности M для данного графа G.

Затем создается массив A, в каждой строке которого содержится множество вершин A[i]. первым элементом этого множества является вершина Xi0, номер которой совпадает с номером строки. Остальные члены этого множества - все вершины данного графа G, смежные первой вершине из этого множества.

Далее с этим массивом A проводятся следующие манипуляции:

Множество вершин A[i] в каждой строке просматривается, начиная со второго элемента Xi1 этого множества A[i], и по матрице смежности M устанавливается, смежна ли данная вершина Xij всем предыдущим вершинам из множества A[i], начиная с первой - Xi0. Если обнаруживается, что одна из вершин Xij при рассмотрении не смежна с другими вершинами Xik (k=0,j-1) этого множества A[i], то она удаляется из этого множества. Продолжается рассмотрение остальных вершин Xij до тех пор, пока множество не рассмотренных вершин не станет пустым. Таким образом, из данного множества вершин A[i], смежных с первой вершиной этого множества - Xi0 будут удалены все те вершины, которые не смежны всем остальным вершинам этого множества A[i]. Таким образом, оставшееся множество вершин A[i] будет являться максимальным полным подграфом от первой вершины этого множества Xi0.

После рассмотрения одного множества A[i] в массиве A рассматриваются следующие, по той же схеме. Из них также удаляются вершины. В конечном счече будет получен массив A, в каждой i-й строке которого будет содержаться максимально полный подграф A[i], возможный от i-й вершины Xi0.

На следующем шаге алгоритма будет создан еще один массив B, содержащий множество целых чисел. Каждый i-й элемент B[i] этого множества B представляет собой количество вершин в соответствующем максимально полном подграфе A[i]. Например если 3-й элемент данного множества равен 5, это означает, что максимально полный подграф, построенный от 3-ей вершины состоит из 5 вершин, включая 3-ю. множество вершин {X30..X34}, которые составляют этот подграф A[3] является мнжеством вершин в 3 строке массива A.

После того, как были созданы массивы A и B, создается линейный список С, каждый элемент которого содержит множество вершин X, составляющих уникальный наибольший полный подграф графа G.

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

Например, если в массиве A имеется следующее множество вершин, состовляющее полный подграф: {2,4,5,7}, что означает, что во 2 строке массива А содержится это множество вершин, состоящее из 4 элементов, массив В содержит 4 одинаковых элемента - 4 по адресам 2,4,5,7. Однако это означает, что в 4, 5 и 7 строках массива А будет содержаться то же самое множество вершин.

Во время формирования списка С этот факт учитывается.

Список формируется следующим образом: в массиве В ищется максимальный элемент bmax. Это целое число, показывающее размер наибольшего полного подграфа графа G. Затем просматривается массив В. И если соответствующий элемент B[i]по адресу i равен bmax, то создается новый элемент в списке, в него заносится наибольший полный подграф из массива А по адресу i. Проводится дальнейший просмотр массива В и ищутся другие подграфы, содержащие bmax вершин. Если таковые находятся (а они обязательно находятся) то на этом этапе выполняется проверка, не добавлено ли уже это множество вершин A[i] в список НПП. Проверка осуществляется следующим образом: список С просматривается сначала, и каждое множество вершин, содержащееся в элементе этого списка сравнивается с множеством A[i]. Если обнаруживается, что такое множество A[i] уже содержится в списке С, то оно пропускается, происходит дальнейшее рассмотрение массива В. В противном случае, если такое множество не было найдено в списке, то создается еще одна ячейка списка С и в нее записывается множество A[i].

Таким образом, после того, как закончится рассмотрение массива В, то есть будут рассмотрены все возможные НПП и уникальные будут добавлены в список С, полученный список С будет содержать в себе все возможные НПП для данного графа G.

.2 Описание логической структуры программы

Программа разбита на отдельные функциональные части - подпрограммы, которые распределяются по отдельным уровням иерархии. Каждая из подпрограмм решает только свою небольшую задачу по преобразованию данных, что позволяет упростить процесс написания и отладки программы в целом. Далее приводится описания назначения всех функций.

Функция WinMain является главной функцией программы, из которой производится вызов остальных функций.

Функция ABOUTDLG является функций всплывающего окна "О программе"_gr - функция ищет наиболее полный подграф от текущей(переданной) вершины и возвращает массив подграфов_podgraf - функция создания конечного списка наибольших полных подграфов(с наибольшим кол-вом вершин).

Функция cr_matr - функция создания и вывода матриц смежности и инцидентности.

Функция paint_podgraf - рисует подграф в области, выделенной для графа. Передается номер графа, который надо нарисовать и список наибольших полных подграфов._mouse - процедура рисования графа мышью.- оконная процедура главного окна программы.

Целью этапа проектирования программы является разработка алгоритмов решения поставленной задачи, т.е. разработка формальной последовательности действий, обеспечивающей получение требуемых результатов для заданных исходных данных. На этом этапе решаются следующие задачи:

разработка алгоритма основной программы;

разработка детальных алгоритмов отдельных подпрограмм;

.        инструкция пользователю.

Для работы с данной программой необходимо выбрать инструмент:

вершина (флажок в диалоговой части окна «Что рисуем?»)

ребро (в этом же окне)

выбрать тип рисуемого графа

ориентированный(флажок в диалоговой части окна «Тип графа»)

неориентированный(в этом же окне)

нажать кнопку «приступить» и начать постреоние графа щелчком мыши в области «Собственно граф. Чертить здесь!»

нажать кнопки «применить изменения»à «Выполнить задачу!»

Для редактирования графа:

нажать кнопку «приступить» и начать редактирование графа(добавление вершин и ребер)

после окончания редактирования нажать кнопки «применить изменения»à «Выполнить задачу!».

Для выхода из программы жмем «Выход».

Данная программа является полностью динамической. Она не нуждается во внешних источниках данных. Входными данными служат вводимые в ходе выполнения программы вершины и соединяющие их ребра.

.3 Решение контрольных примеров

Пример 1, случай, когда все страны соседние.

Рисунок 5- Пример зарисовки графа.

Пример 2, где не все страны между собой являются соседними.

Рисунок 6- Пример зарисовки графа

Заключение

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

раскраска граф алгоритм матрица

Список используемых источников

Аляев Ю.А. , Тюрин С.Ф. Дискретная математика и математическая логика: учебник .- М.:Финансы и статистика, 2006-368с.:ил.

Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб.для вузов/ Под ред. В.С. Зарубина, А.П. Крищенко. - 3-к изд., стереотип.- М.: Изд-во МГТУ им. Н.Э. Баумана, 2004.- 744с. (Сер. Математика в техническом университете; Вып. XIX).

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

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