Задача раскраски. Задачи, возникающие при планировании производства

ЛЕКЦИЯ Задача раскраски Некоторые задачи, возникающие при планировании производства, составлении графиков осмотра и транспортировки товаров, могут быть представлены как известная в теории графов задача раскраски, которая формулируется следующим образом: для данного графа определить минимальное количество цветов, необходимых для раскраски вершин графа таким образом, чтобы никакие две смежные вершины не были окрашены в один цвет. Вершинной раскраской неорграфа G   X ,U  r цветами называется функция CV : X  1,2,..., r, такая, что для любых двух смежных вершин x1 и x2 имеем CV  x1   CV  x2  . Функция CV  x  называется функцией раскраски. Говорят, что граф G допускает раскраску r цветами, если существует функция color с областью значений 1,2,..., r . Хроматическим числом   G  графа G называется наименьшее такое r , при котором граф G допускает вершинную раскраску r цветами. В этом случае граф называется r -хроматическим. Множество вершин одного цвета называется одноцветным классом. Для хроматического числа различными исследователями предложены оценки, перечислим некоторые из них: нижние оценки   G  : n ;  G    G  n2 ;  G   2 n  2m если граф содержит полный подграф на m вершинах, то   G   m ; верхние оценки для   G  :  G   n  1   G  ;   G   1  max di  1. i: xi X  Кроме того, для хроматических чисел графа G и его дополнения G известны следующие неравенства: 2 n   G    G   n  1; 2  n 1 n   G    G     .  2  Реберной раскраской неорграфа G   X ,U  v цветами называется функция CE : U  1,2,..., v , такая, что для любых двух ребер u1 и u2 имеем CE  u1   CE  u2  . Хроматическим индексом графа G   X ,U  называется наименьшее такое v , что граф G допускает реберную раскраску v цветами. Заметим, что задача реберной раскраски решается как задача вершинной раскраски, если от заданного графа G перейти к его реберному графу L  G  , поэтому задача реберной раскраски является избыточной по постановке. Для графов G1   X ,U1  и G2   X ,U 2  с одним и тем же множеством вершин X имеем  G1  G2 1   G1    G2  . Граф называется критическим, если удаление любой из его вершин вместе с инцидентными ребрами приводит к графу с меньшим хроматическим числом. Известно, что всякий критический граф G , являющийся r хроматическим, обладает следующими свойствами: a) G связен; b) степень каждой вершины не меньше  r  1 ; c) не существует вершины, удаление которой приводит к несвязному графу. Рассмотрим некоторые процедуры раскрашивания графа. Эвристическая процедура раскрашивания графа Замечание: Данный алгоритм определяет оценку y  G  хроматического числа   G  графа G , которая удовлетворяет соотношению   G   y  G   max min i, d i   1 , i где d  i   степень i -ой вершины, причем индексация вершин xi осуществляется в соответствии с убыванием их степеней. Шаг 1. Пусть G   X ,U   данный граф. Для каждой вершины xi определить ее степень d i , и упорядочить вершины в порядке невозрастания их степеней, в результате будет сформирован список вершин для просмотра. Шаг 2. Пусть r  номер текущего цвета. Просматривая список от начала к концу будем раскрашивать вершины по правилу: первая неокрашенная вершина в списке окрашивается в цвет r , затем в этот же цвет окрашивается любая другая вершина, которая не смежна с уже окрашенными в данный цвет r. Шаг3. Повторять Шаг 2 для r  1 до тех пор, пока все вершины не будут окрашены, при этом количество использованных цветов определяет приближенное значение хроматического числа; вершины, окрашенные в один цвет образуют одноцветные классы. Пример. Рассмотрим граф, изображенный на рис. 2. Для каждой вершины определим ее степень и составим список вершин. Рисунок 1 – Неорграф G Вершины Степени Цвет f c d a e g 5 1 4 2 4 3 3 3 3 3 1 2 2 3 b Вершину f окрасим в цвет №1. Следующие вершины c, d , a смежны с вершиной f , поэтому их пропускаем. Следующая вершина b не смежна с f , поэтому ее окрашиваем в цвет №1. Оставшиеся вершины e и g смежны с f  они не могут быть окрашены в цвет №1. Не все вершины окрашены, поэтому выбираем следующий цвет №2 и возвращаемся к началу списка. Первая неокрашенная вершина  c , окрашиваем ее в цвет №2. Следующие в списке неокрашенные вершины d и a смежны с c , поэтому их пропускаем. Следующая неокрашенная вершина e не смежна с c , поэтому ее также окрашиваем в цвет №2. Вершина g смежна с e , поэтому не может быть окрашена в цвет №2. Снова не все вершины окрашены, поэтому выбираем краску №3 и возвращаемся к первой неокрашенной вершине. Это вершина d , окрашиваем ее в цвет №3. Следующую неокрашенную вершину также окрашиваем в цвет №3, поскольку она не смежна с d . Следующая неокрашенная в списке вершина g не смежна ни с d , ни с a . Таким образом, все вершины оказались окрашенными, поэтому процесс раскрашивания закончен. Количество использованных красок равно 3, поэтому хроматическое число заданного графа равно 3. Замечание. Процедура позволяет определить лишь приближенное значение хроматического числа, причем примененная к одному и тому же графу она может дать различные варианты раскраски. На рис.1 представлены различные раскраски графа, при этом в первом случае хроматическое число равно 4, а во втором – 3. З С С К О О З К К К С З О С К С К З З З С С О З К С К З К С К С К З З К С З К С Рисунок 2 – Различная раскраска графа (цвета: З – зеленый, С – синий, К – красный, О – оранжевый) Модификация процедуры раскрашивания графа Шаг 1. Положить r  1 (здесь r  приближенное значение хроматического числа). Шаг 2. Пусть G  X   граф на множестве вершин X . Для каждой вершины xi определить степень d i и расположить вершины в порядке невозрастания степеней. Шаг 3. Первая вершина окрашивается в цвет r ; затем, двигаясь по списку, в цвет r окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Пусть S r  множество вершин, окрашенных в цвет r. Шаг 4. Положить X  X \ Sr . Если X   , то на множестве вершин X получить порожденный подграф G  X  . Положить r  r  1 и перейти к шагу 2. Иначе останов  все вершины графа окрашены, r приближенное значение хроматического числа. Данный алгоритм целесообразно использовать, если имеется множество вершин с одинаковыми степенями. Заметим, что после удаления окрашенных вершин к полученному подграфу вновь применяется основная процедура, т.е. определяются степени вершин и формируется новый список. Заметим, что одноцветный класс представляет собой множество попарно не смежных вершин. Такие множества называются независимыми. Независимое множество называется максимальным, если оно не является собственным подмножеством никакого другого независимого множества. Заданный граф может иметь целое семейство максимальных независимых множеств. Мощность независимого множества максимальной мощности (наибольшего независимого множества) называется числом независимости. Если известно, что граф G   X ,U  является r -хроматическим, то он может быть окрашен с использованием r красок на основе следующей процедуры: сначала в один цвет окрашивается некоторое максимальное независимое множество S  X  , затем окрашенные вершины вместе с инцидентными вершинами удаляются из графа и в следующий цвет окрашивается множество S  X \ S  X   и т.д. до тех пор пока не будут раскрашены все вершины. Пример. Рассмотрим граф на рис. 3. Рисунок 3 – Неорграф для раскраски Найдем в нем произвольное максимальное независимое множество, например, S1  b, f , h и окрасим его вершины в цвет 1. Удалим вершины b, f и h из графа вместе с инцидентными ребрами. Получим его подграф на рис. 4. Рисунок 4 – Граф после удаления вершин S1  b, f , h В полученном подграфе вновь найдем максимальное независимое множество, например, S2  c, a , и окрасим его вершины в цвет 2. На рис. 5 представлен подграф, полученный после удаления окрашенных вершин. Рисунок 5  Граф после удаления вершин S2  c, a На рис. 5 видно, что потребуется еще два цвета, чтобы окрасить вершины. Здесь S3  d , g  независимое множество окрашивается в цвет 3. После удаления этих вершин остается единственная изолированная вершина, S4  e и вершина e окрашивается в цвет 4. Таким образом, хроматическое число равно 4; одноцветные классы: b, f , h , c, a , d , g , e . Заметим, что выбор максимальных независимых множеств на каждом шаге произволен, поэтому алгоритм находит некоторую раскраску. При другом выборе в общем случае можно получить другую раскраску.