страница - 0
Алгоритмические вопросы раскраски предфрактальных и фрактальных графов
Кононова Н.В. (knv fm@mail.ru) (1), Кочкаров Р.А. (2)
(1) Ставропольский институт экономики и управления имени О.В. Казначеева, (2) Финансовая академия при Правительстве РФ
Опишем алгоритм, позволяющий находить хроматическое число графа G и раскраску, соответствующую этому числу [1].
ШАГ 1. Положить k = 1. Найти множества вершин SjJ [G], J = 1,..., qj , максимальных k -подграфов графа G . Пусть Q = G] J = 1,..., qk }• Положить J = 1.
графа GJ = V - SJ [G]
s1 [gj
ШАГ 2. Найти максимальное независимое множество S G J
Если такое множество существует, то перейти к шагу 3. Если все такие множества уже найдены, то перейти к шагу 6.
Шаг 3. Вычислить S = SJj [g] u S1 GJ .
Шаг 4. Если S = V, то остановиться. Число k +1 есть хроматическое число графа G . Подмножества, включенные в множество S, дают требуемую раскраску. Если S Ф V, то перейти к шагу 5.
ШАГ 5. (1) Если S с S для некоторого S Е Q, то перейти к шагу 2.
(2)Если S ZD S для некоторых S Е Q , то положить Q = Q - {S} по всем таким S из Q . Положить Q = Q U {S} и перейти к шагу 2.
(3)Если не выполняется ни одно из условий (1) и (2), указанных выше, то положить Q = Q U {S} и перейти к шагу 2.
Шаг 6. Если j < qj, то положить j = j +1 и перейти к шагу 2.
Если J = qj, то положить J = 1, k = k +1, qj = числу множеств в Q и перейти к шагу 2.
Если работу алгоритма не завершать при первом выполнении условия S = V на шаге 4, то алгоритмический процесс будет продолжаться до получения раскраски в k +1 цветов, если такая раскраска существует. Следует отметить, однако, что описанный алгоритм не дает полного перечисления всех возможных раскрасок в k +1 цветов, а только порождает оптимальные независимые раскраски. Такие раскраски могут оказаться только небольшой частью всех возможных раскрасок в k + 1 цветов.
Для определения хроматического числа графа может быть использован с поразительной эффективностью очень простой метод неявного перебора, использующий дерево поиска [1]. Метод состоит в следующем.
Предположим, что множество вершин как-то упорядочено Vj - i -я вершина этого множества. Тогда первоначальная допустимая раскраска может быть получена так:
(1)окрасить Vi в цвет 1.
(2)каждую из оставшихся вершин окрашивать последовательно, в соответствие с заданным упорядочением: вершина Vi окрашивается в цвет с наименьшим возможным «номером».
Пусть k - число цветов, требуемое для вышеупомянутой раскраски. Если существует раскраска, использующая только k - 1 цветов, то все вершины, окрашенные в цвет k,
должны быть перекрашены в цвет J < к. Пусть v.* - первая вершина при заданном
упорядочении, которая была окрашена в цвет к. Поскольку (согласно (2)) она была так окрашена потому, что не могла быть окрашена в цвет J < к , то ее можно перекрасить в цвет
J < к, лишь перекрасив предварительно хотя бы одну из смежных с ней вершин. Итак, шаг
возвращения из вершины v.* можно осуществить следующим образом.
Из смежных с v.* вершин в множестве {vi,...,vi} найти последнюю, т. е. вершину с наибольшим индексом. Пусть это будет вершина vr. Если vr окрашена в цвет Jr, то перекрашивается в другой допустимый цвет с наименьшим возможным «номером» jr, таким, что j[ > Jr +1. Если jr < к, то надо продолжать последовательно перекрашивать все вершины с vr+1 до vn, применяя указанное выше правило (2) и помня о том, что цвет к использовать нельзя. Если такая процедура осуществима, то будет найдена новая лучшая раскраска, использующая меньше, чем к цветов. В противном случае, т. е. если встретится вершина, «требующая» цвет к, то можно снова сделать шаг возвращения - из такой вершины. Если J = к или нет другого допустимого цвета Jr, то можно сразу же делать шаг возвращения из вершины vr . Алгоритм заканчивает работу, когда на шаге возвращения достигается вершина v1 .
Далее предлагается последовательный метод, основанный на упорядочивании множества вершин. В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней. Первая вершина окрашивается в цвет 1; затем список вершин просматривается сверху вниз и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа.
В этом алгоритме если две вершины имеют одинаковые степени, то их взаимное положение в списке случайно. В таких ситуациях уточнение в размещении вершин можно осуществлять
- л (2)
с помощью двухшаговых степеней а> вершин vt, имеющих одинаковые степени
(2)
(одинаковые 1-шаговые степени), где di определяется как число маршрутов длины 2, исходящих из vt. Эти вершины могут быть размещены тогда в соответствии с величинами
(2)
степеней d\ . Если все-таки найдутся вершины, у которых совпадают и степени dt
и
степени d2, то можно вычислить трехшаговые степени d3) (определяемые аналогичным
образом) и разместить вершины с учетом степеней di(3) и т. д.
Можно действовать иначе: размещать вершины сразу в соответствии с их степенями
( 2 )(3)
di или степенями di и применять тот же самый последовательный метод раскраски.
Таким образом, описанный выше метод раскрашивания очерчивает целый класс последовательных методов, каждый из которых связан с определенным способом упорядочивания вершин, либо статическим, т. е. фиксированным сразу для всей процедуры, либо динамическим, т. е. изменяющимся в процессе раскраски. Способ упорядочивания может базироваться на многих возможных критериях, зависящих от степеней вершин или от каких-либо других родственных характеристик.
Рассмотрим предфрактальный граф GL = (VL, EL), смежность старых ребер которого сохраняется [2]. Пусть GL = (VL, EL ) порожден затравкой H = (W, Q) - полный граф, у которой W = n , Q = q. Опишем принцип работы алгоритма в.
Поскольку порождающая затравка H = (W , Q) является полным графом, то для ее правильной и одновременно минимальной раскраски понадобится ровно n цветов, то есть хроматическое число %(H) = n. Отметим, что для раскраски затравки H, достаточно
последовательно окрашивать ее вершины в цвета 1,2,...,n. В начале алгоритма окрашивается подграф-затравка первого ранга z1), аналогом которой является граф G1 из
траектории G1,G2,...,GL или затравка H. Для раскраски подграф-затравки z1)
понадобится n цветов, как объяснялось ранее. Далее рассмотрим подграф-затравки второго
ранга . У каждой из них одна вершина оказалась окрашенной, так как подграф-затравка
первого ранга имеет одну общую вершину с подграф-затравкой второго ранга, в силу того,
(2)
что смежность старых ребер сохраняется. Рассмотрим подграф-затравку 2у , одна из ее вершин оказалась окрашенной, например, в цвет 1. Поскольку любая подграф-затравка по
(2)
сути затравка H , окрасим вершины в оставшиеся цвета 2,3,...,n . Окрасим таким же
(2)
образом все подграф-затравки второго ранга z . Далее рассматриваем подграф-затравки
s2
третьего ранга z , у каждой из них оказалось окрашенной по одной вершине. Окрашиваем
s3
подграф-затравки в соответствие с описанным раннее. Продолжая окрашивать подграф-
s3
затравки следующих рангов до L -го ранга включительно, получим правильную n -раскраску предфрактального графа Gl . Представим алгоритм 1 в рекуррентной форме, используем для этого процедуру РАСКРАСКА.
АЛГОРИТМ в1. Вход: предфрактальный граф Gl = (Vl , El ). Выход: правильная n-раскраска.
ШАГ 1. Окрасить одну из вершин подграф-затравки z1(1) в цвет 1.
ШАГ 2. Раскрасить подграф-затравку z1(1) используя процедуру РАСКРАСКА. Процедура Раскраска.
Вход: подграф затравка z).
si
Выход: n-раскраска.
ШАГ 1. Последовательно раскрасить все вершины подграф-затравки в n цвета, начиная с вновь окрашенной.
Шаг 2. Если I < L то: Используя процедуру Раскраска раскрасить подграф-затравки z1+1)
л1+1
следующего ранга, для всех S[+1 = 1,2,...,nl. ЕСЛИ I = L ТО: Закончить процедуру и вернуться.
содержание:
[стр.Введение] [стр.1] [стр.2] [стр.3]