Алгоритм раскраски графа с перекраской двуцветных компонент
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Аннотация
Выпускная квалификационная работа посвящена алгоритмическим проблемам задачи о правильной раскраске вершин графа, которая относится к классу NP-полных задач. В работе изучается эвристический алгоритм раскраски вершин графа с перекраской двуцветных компонент. Алгоритм запрограммирован на языке Си++ в среде программирования MicrosoftVisualStudio 2010, получены численные результаты.
Введение
произвольный граф алгоритм
Разнообразные задачи, возникающие при планировании производства, составлении графиков осмотра, хранении и транспортировке товаров и т. д., могут быть представлены часто как задачи теории графов, тесно связанные с так называемой задачей раскраски.
Пусть G=(V,E) - обыкновенный граф, то есть неориентированный граф без кратных ребер и петель. Раскраской вершин графа называется назначение цветов его вершинам.Обычно цвета - это числа . Раскраска называется правильной, если каждый цветной класс является независимым множеством (независимое множествовершин графа -это любое множество попарно не смежных вершин, т.е. множество вершин, порождающее пустой подграф). Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа Gс наименьшим числом цветов.Это число называется хроматическим числомграфа G, то есть это минимальное число цветов, требующееся для раскраски G.
Хроматическое число графа нельзя найти, зная только числа вершин и ребер графа. Недостаточно также знать степень каждой вершины, чтобы вычислить хроматическое число графа. В этом можно убедиться, рассматривая графы, приведенные на рис. 1(a) и 1(6). Эти графы имеют по вершин, ребер и одинаковые распределения степеней вершин . Однако хроматические числа данных графов равны 4 и 2 соответственно. При известных величинах n (число вершин), m (число ребер) и (степени вершин графа) можно получить верхнюю и нижнюю оценки для хроматического числа графа. Некоторые оценки хроматического числа мы рассмотрим ниже.
Задача нахождения хроматического числа произвольного графа явилась предметом многих исследований в конце XIX и в последующих столетиях. Сейчас по этому вопросу известно большое количество интересных результатов. Но мы не будем углубляться в эти результаты.
Так же задача нахождения хроматического числа графа вошла в знаменитый список из 21 NP - полной задачи, предложенный в 1972 году Р. Карпом. Поэтому, все известные алгоритмы, которые находят минимальную раскраску для любого графа, требуют экспоненциального числа шагов. Таким образом, все исследования, связанные с разработкой алгоритмов правильной раскраски графов, следует развивать в двух направлениях:
) нахождение точных полиномиальных алгоритмов для ограниченных классов графов;
Рисунок1. Два графа с одинаковыми n,m и распределениями степеней вершин, но с различными хроматическими числами, (а) ?(G)=4, (б) ?(G)=2
) получение приближенных алгоритмов (полиномиальных) таких, которые гарантируют раскрашивание графа для некоторого из интервала , где - число вершин G.
В данной выпускной квалификационной работе бакалавра для исследования был выбран приближенный алгоритм раскраски вершин графа с перекраской двуцветных подграфов.
Задача раскраски вершин графа. Некоторые примеры раскраски графа
Задача о раскраске вершин графа, как было приведено выше, заключается в том, что бы раскрасить вершины графа так, чтобы любые две смежные вершины были раскрашены в разные цвета, при этом число использованных цветов должно быть наименьшим.
Но задача раскраски в том чистом виде, в каком она рассматривается в теории, редко встречается на практике. Однако ее обобщения и разновидности (незначительно отличающиеся от нее) находят широкое применение в большом числе различных прикладных задач. Ниже приведены некоторые примеры раскраски, часто встречающиеся на практике. Естественно, что данный список этими примерами не ограничивается.
Составление графиков осмотра (проверки)
В задачах теории расписанийосмотры представляются, в виде временных интервалов. Каждому осмотру можно сопоставить вершину некоторого графа, причем две любые вершины графа будут соединены ребром лишь тогда, когда соответствующие им осмотры нельзя осуществлять одновременно. Требуется составить такой график осмотра, который связан с наименьшими временными затратами (с учетом приведенных выше ограничений на совместимость осмотров). Эта задача эквивалентна задаче о раскраске вершин графа с использованием наименьшего числа цветов. Хроматическое число графа как раз и соответствует осмотру, требующему наименьших временных затрат.
Распределение ресурсов
Пусть для выполнения каких-то n работ надо распределить m имеющихся в наличии ресурсов. Считаем, что каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и что для выполнения i-й работы требуется подмножество ресурсов Si.
Построим граф G: каждой работе соответствует определенная вершина графа, а ребросуществует в графе тогда и только тогда, когда для выполнения и работ требуется хотя бы один общий ресурс, т. е. когда . Это означает, что i-я и работы не могут выполняться одновременно. Раскраска графа определяет тогда некоторое распределение ресурсов (по выполняемым работам), причем такое, что работы, соответствующие вершинам одного цве?/p>