Алгоритм раскраски графа с перекраской двуцветных компонент

Этапы нахождения хроматического числа произвольного графа. Анализ примеров раскраски графа. Характеристика трудоемкости алгоритма раскраски вершин графа Мейниеля. Особенности графов, удовлетворяющих структуру графов Мейниеля, основные классы графов.
Краткое сожержание материала:

Размещено на

Аннотация

Выпускная квалификационная работа посвящена алгоритмическим проблемам задачи о правильной раскраске вершин графа, которая относится к классу NP-полных задач. В работе изучается эвристический алгоритм раскраски вершин графа с перекраской двуцветных компонент. Алгоритм запрограммирован на языке Си++ в среде программирования MicrosoftVisualStudio 2010, получены численные результаты.



Введение

произвольный граф алгоритм

Разнообразные задачи, возникающие при планировании производства, составлении графиков осмотра, хранении и транспортировке товаров и т. д., могут быть представлены часто как задачи теории графов, тесно связанные с так называемой «задачей раскраски».

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

Хроматическое число графа нельзя найти, зная только числа вершин и ребер графа. Недостаточно также знать степень каждой вершины, чтобы вычислить хроматическое число графа. В этом можно убедиться, рассматривая графы, приведенные на рис. 1(a) и 1(6). Эти графы имеют по вершин, ребер и одинаковые распределения степеней вершин . Однако хроматические числа данных графов равны 4 и 2 соответственно. При известных величинах n (число вершин), m (число ребер) и (степени вершин графа) можно получить верхнюю и нижнюю оценки для хроматического числа графа. Некоторые оценки хроматического числа мы рассмотрим ниже.

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

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

1) нахождение точных полиномиальных алгоритмов для ограниченных классов графов;

Рисунок1. Два графа с одинаковыми n,m и распределениями степеней вершин, но с различными хроматическими числами, (а) ч(G)=4, (б) ч(G)=2

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

В данной выпускной квалификационной работе бакалавра для исследования был выбран приближенный алгоритм раскраски вершин графа с перекраской двуцветных подграфов.



Задача раскраски вершин графа. Некоторые примеры раскраски графа

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

Но задача раскраски в том «чистом» виде, в каком она рассматривается в теории, редко встречается на практике. Однако ее обобщения и разновидности (незначительно отличающиеся от нее) находят широкое применение в большом числе различных прикладных задач. Ниже приведены некоторые примеры раскраски, часто встречающиеся на практике. Естественно, что данный список этими примерами не ограничивается.

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

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

Распределение ресурсов

Пусть для выполнения каких-то n работ надо распределить m имеющихся в наличии ресурсов. Считаем, что каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и что для выполнения i-й работы требуется подмножество ресурсов S_i.

Построим граф G: каждой работе соответствует определенная вершина графа, а ребросуществует в графе тогда и только тогда, когда для выполнения и работ требуется хотя бы один общий ресурс, т. е. когда . Это означает, что i-я и работы не могут выполняться одновременно. Раскраска графа определяет тогда некоторое распределение ресурсов (по выполняемым работам), причем такое, что работы, соответствующие вершинам одного цвета, выполняются одновременно. Наилучшее использование ресурсов (т. е. выполнение всех n работ за наименьшее время) достигается при оптимальной раскраске вершин графа .

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

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

Задача распределения оборудования

Заданы множества и работ и механизмов соответственно. Для выполнения каждой из работ требуется некоторое время, одинаковое для всех работ, и некоторые механизмы. При этом никакой из механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы общее время выполнения всех работ было минимальным.

Построим граф G, положив VG= Vи объявив вершины v_iи v_jсмежными тогда и только тогда, когда для выполнения работ v_iи v_j требуется хотя бы один общий механизм. При правильной раскраске графа Gработы, соответствующие вершинам одного цвета, можно выполнять одновременно, а наименьшее время выполнения всех работ достигается при минимальной раскраске.

Оценки хроматического числа

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

Обозначим через множество всех порожденных подграфовПорождённый подграф -- подграф, порождённый множеством вершин исходного графа. графа G, а через д(G) - минимальную из степеней вершин графа G.

Теорема 1.Для любого графаG верно неравенство

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

Предположим, что . Граф правильно раскрасим цветами. Окрасив затем вершину в один из этих цветов, не использованный при окраске смежных с ней вершин, получим правильную - раскраску графа . Следовательно, и

Обозначим черезнаибольшую из степеней вершин графа .

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

.

Доказательство. Даны различных цветов, получим - раскраску графа G следующим образом.

Возьмем произвольную вершину и присвоим ей любой из цветов. Затем выберем нераскрашенную вершину, например . Присвоим вершине цвет, который не был присвоен смежным с ней вершинам. Это вс...