Раскраска графов

Дискретная математика Раскраска графов Преподаватель: Шилова З.В. 1. Основные понятия. Хроматическое число Характерным специфическим направлением теории графов является цикл задач, связанный с раскрасками графов, в котором изучаются разбиения множества вершин , обладающие определенными свойствами, например, смежные вершины должны принадлежать различным множествам (вершины или ребра из одного множества окрашиваются одним цветом). При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Другое применение раскраски в графах может быть использовано при:  распределение памяти в ЭВМ;  проектирование сетей телевизионного вещания;  распределение частот и областей сотовых систем связи. Задача об определении минимального числа красок, нужных для правильной раскраски графа, которую рассмотрим, является одной из первых задач теории графов. При этом рассматриваемый граф должен быть полностью неориентированный без кратных ребер и петель. Виды раскрасок Раскраска вершин. Терминология, в которой метки называются цветами, происходит от раскраски политических карт. Такие метки как красный или синий используются только когда число цветов мало, обычно же подразумевается, что метки являются целыми числами {1,2,3,...}. Раскраска с использованием k цветов называется k-раскраской. Определение. Наименьшее число цветов, необходимое для раскраски графа G называется его хроматическим числом и часто записывается как X(G). Подмножество вершин, выделенных одним цветом, называется цветовым классом, каждый такой класс формирует независимый набор. Таким образом, k-раскраска - это то же самое, что и разделение вершин на k независимых наборов. Рёберная раскраска Рисунок 1 - Рёберная раскраска графа в красный, синий и зелёный цвета. Рёберная 3-цветная раскраска В теории графов рёберной раскраской графа называется назначение «цветов» рёбрам графа таким образом, что никакие два сопряжённых ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в k различных цветов для заданного значения k или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс три. Пример - Построение раскраски графа K8 в 7 цветов Рисунок 2 - Граф может быть раскрашен 3 цветами 12 способами Хроматический многочлен Хроматический многочлен считает число возможных вариантов раскраски графа с использованием не более чем заданного числа цветов. Например, граф на рисунке 2 может может быть раскрашен 12 способами с использованием 3 цветов. Двумя цветами он не может быть окрашен в принципе. 2. Алгоритмы раскраски графа Алгоритм раскраски графа позволяет находить (точное или приближенное) значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин. Граф G называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является rхроматическим, называется хроматическим числом графа G. Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин. Жадный алгоритм упорядочивает вершины и последовательно присваивает вершине наименьший доступный цвет, не использовавшийся для окраски соседей, либо добавляет новый. Качество полученной раскраски зависит от выбранного порядка. Раскраска графа по степеням вершин Алгоритм 1. Упорядочить вершины по степеням начиная с наибольшей степени вершины. 2. Задать начальное значение счетчика k=1. 3. Первую вершину окрашиваем в цвет k и заносим в B(k). 4. Просматриваем следующую неокрашенную вершину, если она несмежная с вершинами B(k) то окрашиваем ее в цвет k, иначе пропускаем. 5. Проверяем количество просмотренных вершин, если i n (iномер текущей вершины), то возврат в п.4, иначе k=k+1 и просмотр списка начинается заново исключая окрашенные вершины. 6. Проверка на окончание поиска: если неокрашенных вершин не осталось, то конец поиска, иначе п.5. Пример: задан граф 2 Раскрасить по степеням вершин 3 1 4 8 6 Составим таблицу: 5 Верш Степ ина ень vi  4 5 6 5 3 4 2 4 5 4 7 4 8 3 9 3 1 2 Цвет  B(1) B(2) B(3) B(4) к з ж з ж с к ж к 1 2 3 4 7 9 В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней. Первая вершина окрашивается в цвет 1; затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа. Алгоритм с использованием независимого множества вершин Независимое множество вершин S – это такое подмножество вершин, в котором никакие две вершины этого подмножества не соединены ребром.  Максимальное независимое множество вершин Smax - это независимое множество вершин, не являющееся собственным подмножеством никакого другого независимого множества вершин. Оно содержит наибольшее число вершин. В графе может быть несколько Smax.. Для отыскания Smax существует несколько методов. Точный метод основан на булевой алгебре. Он достаточно сложен. Рассмотрим приближенный метод Метод выбора Smax из нескольких S: от каждой вершины графа определяются все независимые множества вершин, из которых выбирается множество с максимальной мощностью. Алгоритм определения независимого множества S 1. 2. 3. Выбирается начальная вершина v0 и заносится в S. Рассматривается следующая вершина vi , если vi несмежная с S, то она включается в S, иначе не включается. Проверка на окончание: если просмотрены все вершины, то – конец, иначе п.2. Алгоритм раскраски с использованием независимого множества вершин Рассмотрим следующую схему рекурсивной процедуры Р: 1. Выбрать в графе G некоторое максимальное независимое множество вершин Smax. 2. Окрасить вершины множества Smax в очередной цвет. 3. Применить процедуру Р к графу G\ Smax. Пример: задан граф Раскрасить с использованием независимых множеств вершин Определим Smax Smax1={1,3,7} – 1 цвет Smax2={4,9} – 2 цвет Smax3={5,8} – 3 цвет Smax4={2,6} – 4 цвет