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

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

Д (х*) И, кроме того, в выборе вершины xi из множества Г (х*) П Qk- Такой выбор вершины Xi будет приводить на шаге возвращения к уменьшению величины А (х*) - каждый раз на единицу - до тех пор, пока вершина х* не станет удовлетворять условию (3.8) при выполнении шага возвращения.

Следует отметить, что поскольку на шаге возвращения вершина Xi попадает в Ql, то может оказаться, что при этом новом входе значение величины А меньше, чем для ранее фиксированной вершины X*. Значит, надо проверить, не ускорит ли эта новая вершина выполнение условия (3.8). Это особенно важно в начале ветвления, когда Qh = 0-

2.3.2. Описание алгоритма

Начальная установка

Шаг 1. Пусть S=Q- = 0, = Z, А; = 0. Прямой шаг

Шаг 2. Выбрать вершину xi £ Qt, как упоминалось ранее, и сформировать 5+1, +1 и Qu+u оставляя Ql и Q% нетронутыми. Положить к = к \.

Проверка

Шаг 3. Если удовлетворяется условие (3.8), то перейти к шагу 5, иначе к шагу 4.

Шаг 4. Если Qt = Qh - 0, то напечатать максимальное независимое множество и перейти к шагу 5. Если Qt - 0, а Ql Ф ф 0, то перейти к шагу 5. Иначе перейти к шагу 2.

Шаг возвращения

Шаг 5. Положить к = к - 1. Удалить xi из S+i чтобы получить Sk- Исправить Ql и Qt, удалив вершину xi из Qt и добавив ее к Ql. Если к = Ow.Q* - 0, то остановиться. (К этому моменту будут уже напечатаны все максимальные независимые множества.) Иначе перейти к шагу 3.

Комментарий по применению описанного выше алгоритма приведен в [14] вместе с программой, написанной на Алголе. Эта программа была опробована для большого числа графов (в частности, для графов Муна-Мозера, см. задачу 10) и было установлено, что время, необходимое для построения максимального независимого множества, почти постоянно и не зависит от размера графа. Все это говорит о том, что данный алгоритм является одним из лучших.

4 Н. Кристофидес



3. Доминирующие множества

Для графа G = (Х, Г) доминирующее множество вершин (называемое также внешне устойчивым множеством [11]) есть множество вершин S X, выбранное так, что для каждой вершины Xj, не входящей в S, существует дуга, идущая из некоторой вершины множества S в вершину Xj.

Таким образом, S есть доминирующее множество вершин (или просто доминирующее множество, когда нет опасности возникновения путаницы), если

S[]T(S) = X (3.10)

Для графа, приведенного на рис. 3.2, множества вершин {xi, х^, Хб}, {xi, Xi}, {xs, Xs, Xs} являются доминирующими множествами.

Доминирующее множество называется минимальным, если нет другого доминирующего множества, содержащегося в нем.


Рис. 3.2.

Таким образом, множество S является минимальным доминирующим множеством, если оно удовлетворяет соотношению (3.10) и нет собственного подмножества в S, которое удовлетворяет условию, аналогичному (3.10). Так, например, для графа, приведенного на рис. 3.2, множество {xi, Xi} - минимальное, а {xi, х^, Xg} нет. Минимальным доминирующим множеством является также множество {хд, х^, х^}, и еще существует несколько таких множеств в этом графе. Следовательно, как и в случае максимальных независимых множеств, в графе может быть несколько минимальных доминирующих множеств, и они не обязательно содержат одинаковое число вершин.



Если Р - семейство всех минимальных доминирующих множеств графа, ТО число

P[G] = min5 (3,11)

Sep

называется числом доминирования ) графа G, а множество S*, на котором достигается минимум, называется наименьшим доминирующим множеством.

Для графа, приведенного на рис. 3.2, наименьшим доминирующим множеством является множество {xi, х^ и, следовательно, р [G] = 2.

3.1. Пример. Размещение центров , покрывающих заданную область

Задач такого типа весьма много. К ним относятся:

(а) Размещение телевизионных или радиопередающих станций на некоторой территории.

(б) Размещение военных баз, контролирующих данную территорию.

(в) Размещение центров торговли, обслуживающих некоторый район.

Предположим, что территория, представленная большим квадратом на рис. 3.3fa), разделена на 16 районов, как показано

Ю

И


Рис. 3.3.

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

1) В оригинале -dominance питЬег .- Прим. ред.



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