Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 [ 28 ] 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141


Рис. 4.4. Граф из примера 3.3.1.

Решение задачи о покрытии для этой матрицы состоит из 4 столбцов и не является единственным. Например, решениями будут множества столбцов (4, 6, 10, 14}, (4, 6, 10, 12}, (4, 6, 10, 11}, (4, 6, 10, 8} и (4, 6, 10, 2}. Если мы выберем последнее из этих решений (отмеченное стрелками) и сопоставим цвета о, Ь, с, d столбцам 4, 6, 10 и 2 соответственно, то вершину xj (принадлежащую одновременно столбцам 2 и 4) можно окрасить в цвет а или в цвет d, а вершину Хд (принадлежащую обоим столбцам 2 и 10) можно окрасить в цвет с или в цвет d и таким образом получить различные оптимальные раскраски.

Интересно отметить, что в данном примере нижняя оценка для у [G] равна 4 (это можно получить из соотношения (4.2), так как а [G] = 3 и и = 10) и, значит, совпадает с истинным значением у [G].

3.4. Алгоритм прямого неявного перебора, использующий дерево поиска

Для определения хроматического числа графа может быть использован с поразительной эффективностью очень простой метод неявного перебора, не содержащий никаких хитростей [4, 9]. Метод состоит в следующем.



Предположим, что множество вершин как-то упорядочено я Xi - i-я вершина этого множества. Тогда первоначальная допустимая раскраска может быть получена так:

(i) окрасить Xi в цвет 1.

(ii) каждую из оставшихся вершин окрашивать последовательно ): вершина Xi окрашивается в цвет с наименьшим возможным номером (т. е. выбираемы!! цвет должен быть первым в данном упорядочении цветом, не использованным при окраске какой-либо вершины, смежной с Xi).

Пусть д - число цветов, требуемое для вышеупомянутой раскраски. Если существует раскраска, использующая только д - 1 цветов, то все вершины, окрашенные в цвет д, должны быть перекрашены в цвет j < д. Пусть хц, - первая вершина при заданном упорядочении, которая была окрашена в цветд'. Поскольку (согласно (ii)) она была так окрашена потому, что не могла быть окрашена в цвет / <; д, то ее можно перекрасить в цвет / <; д, лишь перекрасив предварительно хотя бы одну из смежных с ней вершин. Итак, шаг возвращения из вершины Xi* можно осуществить следующим образом.

Из смежных с х,. вершин в множестве {х^, . . ., Xi* i} найти последнюю (при заданном упорядочении), т. е. вершину с наибольшим индексом. Пусть это будет вершина х^. Если Хц окрашена в цвет 7й, то Xk перекрашивается в другой допустимый цвет с наименьшим возможным номером /д, таким, что jh, ~] -г 1.

Если /ft <; д, то надо продолжать последовательно перекрашивать все вершины с x+i до аг , применяя указанное выше правило (ii) и помня о том, что цвет д использовать нельзя. Если такая процедура осуществима, то будет найдена новая лучшая раскраска, использующая меньше, чем д цветов. В противном случае, т. е. если встретится вершина, требующая цвет д, то можно снова сделать шаг возвращения - из такой вершины.

Если /ft = д или нет другого допустимого цвета / (см. ниже замечание (а)), то можно сразу же делать шаг возвращения из вершины Xk- Алгоритм заканчивает работу, когда на шаге возвращения достигается вершина х^.

Следующие замечания могут помочь ускорить вышеприведенную процедуру прямого неявного перебора.

(а) При любом упорядочении вершин допустимые цвета / для вершины Xi удовлетворяют условию / i (если i < д). Это очевидно, так как вершине Xi предшествуют (при данном упорядочении) только i - 1 вершин и, следовательно, никакой цвет / > t не использовался. Таким образом, для вершины х^ допустимым является то.чько цвет 1, для х^ - цвет 1 и цвет 2 (если х^ смежна с х^, то для допустим только цвет 2) и т. д.

1) В соответствии с заданным упорядочением.- Прим. ред.



(б) Из замечания (а) следует, что с вычислительной точки зрения выгодно располагать переменные в таком порядке, чтобы, например, первые р вершин образовывали наибольшую клику графа G. Это приведет к тому, что каждая вершина (1 i р) будет иметь только один допустимый цвет, т. е. цвет i, и алгоритм может закончить работу раньше, когда на шаге возвращения будет достигнута вершина Хр.

Хотя процедура неявного перебора, описанная в этом разделе, является примитивным древовидным поиском (в котором не нужно вычислять никакие оценки для ограничения ветвлений), тем не менее она нисколько не хуже других известных методов раскраски графов. Так, например, для графа с 30 вершинами, содержащего приблизительно третью часть множества всех ребер полного 30-вершинного графа, нахождение оптимальной раскраски с помощью алгоритма неявного перебора требует около 30 с машинного времени на вычислительной машине IBM ИЗО.

4. Приближенные алгоритмы раскрашивания

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

4.1. Последовательные методы, основанные на упорядочивании множества вершин

В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней.

Первая вершина окрашивается в цвет 1; затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа [23, -25].

Простая модификация описанной выше эвристической процедуры состоит в переупорядочивании неокрашенных вершин



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 [ 28 ] 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95