Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[113]

ны. В самом деле, пусть А и В - ацикличные подграфы G, причём \В\ > А. Из теоремы 5.2 следует, что лес с к рёбрами является несвязным объединением \V\ - к деревьев, где \V\ - количество вершин (независимое доказательство: начнём с леса, состоящего из \V\ вершин и не имеющего ребер, и будем по одному добавлять рёбра, не нарушая ацикличности; тогда добавление каждого ребра уменьшает количество связных компонент на единицу). Следовательно, лес А состоит из \V\ - \А\ деревьев, а лес В - из \V\ - \В\ деревьев. Поскольку \V\ - \В\ < \V\ - \А\, лес В содержит такое дерево Г, что две его вершины принадлежат разным связным компонентам леса А. Более того, поскольку Г связно, оно должно содержать такое ребро (и, v), что и и v принадлежат разным связным компонентам леса А. Следовательно, добавление этого ребра к лесу А не может создать цикла, и его можно взять в качестве элемента ж из определения матроида.□

(Графовые матроиды являются частным случаем матричных, если ребро графа рассматривать как формальную сумму его вершин с коэффициентами в поле вычетов по модулю 2, см. задачу 17-26.)

Если М = (S,I) - матроид, то элемент х А £ X называется независимым от A (extension of А), если множество A U {ж} независимо. Например, в графовом матроиде ребро е независимо от леса А тогда и только тогда, когда его добавление к А не создаёт цикла.

Независимое подмножество в матроиде называется максимальным (maximal), если оно не содержится ни в каком большем независимом подмножестве. Часто бывает полезна следующая

Теорема 17.6. Все максимальные независимые подмножества данного матроида состоят из одинакового числа элементов.

Доказательство. Пусть А и В - максимальные независимые подмножества. Если, скажем, А < \В\, то из свойства замены вытекает существование такого ж А, что A U {ж} независимо - в противоречие с максимальностью.□

В качестве примера рассмотрим графовый матроид Mq, соответствующий связному графу G. Всякое максимальное независимое подмножество Mq должно быть деревом с \V\ - 1 ребром, соединяющим все вершины G. Такое дерево называется покрывающим (остовным) деревом графа G (по-английски spanning tree).

Будем называть матроид М = (S,I) взвешенным (weighted), если на множестве S задана весовая функция w со значениями во множестве положительных чисел. Функция w распространяется по аддитивности на все подмножества множества S; вес подмножества определяется как сумма весов его элементов: w(A) = 2xew(x). Пример: если Mq - графовый матроид, a w(e) - длина ребра е, то w(A) - сумма длин рёбер подграфа А.


17.4.2. Жадные алгоритмы для взвешенного матроида

Многие оптимизационные задачи, решаемые жадными алгоритмами, сводятся к задаче о нахождении в данном взвешенном матроиде М = (S,I) независимого подмножества А С М максимального веса. Независимое подмножество максимального веса называется оптимальным (optimal) подмножеством взвешенного матроида. Поскольку веса всех элементов положительны, оптимальное подмножество автоматически будет максимальным независимым подмножеством.

Например, задача о наименьшем покрывающем дереве

(minimum-spanning-tree problem) состоит в следующем. Дан связный неориентированный граф G = (V, Е) и функция w из множества его рёбер во множество положительных чисел (w(e) будем называть длиной ребра е). Требуется найти множество рёбер, соединяющих все вершины и имеющих наименьшую суммарную длину. Эту задачу можно рассматривать как частный случай задачи об оптимальном подмножестве взвешенного матроида. В самом деле, выберем число wo, строго большее длин всех рёбер, и введем на графовом матроиде Mq веса по правилу w(e) = wq - w(e). Для всякого максимального независимого подмножества (т.е. покрывающего дерева) А имеем

w(A) = (\V\ - l)w0-w(A),

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

Задача о наименьшем покрывающем дереве подробно рассматривается в главе 24; сейчас мы приведём жадный алгоритм, находящий оптимальное подмножество А в любом взвешенном матроиде М. Если М = (S,l), то мы пишем S = S[M] и I = 1[М]; весовая функция обозначается w.

Greedy (М, w)

1А([)

2отсортировать S[M] в порядке невозрастания весов

3for х G S[M] (перебираем все х в указанном порядке)

4do if AU {ж} G 1[М]

5then А <- All {ж}

6return А

Алгоритм работает следующим образом. Полагаем А = 0 (строка 1; пустое множество, как мы помним, всегда независимо) и перебираем элементы S[M] в порядке убывания веса; если очередной элемент можно, не нарушая независимости, добавить к множеству А, то мы это делаем. Ясно, что полученное в результате


множество будет независимым. Ниже мы покажем, что оно действительно будет иметь максимальный вес среди независимых подмножеств, а пока что оценим время работы алгоритма Greedy. Сортировка (строка 2) занимает время O(ralogra), где п = \S\. Проверка независимости множества (строка 4) проводится п раз; если каждая такая проверка занимает время f(n), то общее время работы будет 0(n\ogn + nf(n)).

Теперь покажем, что алгоритм Greedy действительно даёт оптимальное подмножество.

Лемма 17.7 (свойство жадного выбора для матроидов).

Пусть М = (S,I) - взвешенный матроид с весовой функцией w. Пусть ж £ S - элемент наибольшего веса во множестве {у £ S : {у} независимо}. Тогда х содержится в некотором оптимальном подмножестве ACS.

Доказательство. Пусть В - какое-то оптимальное подмножество. Будем считать, что х В, иначе доказывать нечего.

Положим А = {ж}. Это множество независимо по выбору ж. Применяя \В\ - 1 раз свойство замены, мы расширяем А элементами из В и в конце концов построим независимое множество А, состоящее из ж и \В\ - 1 элемента множества В. Имеем А = \В\ (так что А максимально) и w(A) = w(B) - w(y) + w(x), где у - единственный элемент В, не входящий в А. В то же время для всякого у £ В множество {у} независимо в силу свойства наследственности, так что w(x) w(y) по выбору ж. Стало быть, w(A) w(B), и множество А также оптимально. Всё доказано.□

Далее, имеет место следующая очевидная

Лемма 17.8. Если М = (S,I) - матроид, ж £ S и {ж} 1, то

A U {ж} 1 для всех ACS.

Наша последняя лемма такова:

Лемма 17.9 (свойство оптимальности подзадач для матроидов).

Пусть М = (S,T) - взвешенный матроид, и пусть ж £ S - некоторый его элемент, причём множество {ж} независимо. Тогда независимое множество наибольшего веса, содержащее х, является объединением {ж} и независимого множества наибольшего веса в матроиде М = (S,11), где, по определению,

s = {yeS:{x,y}ei},

1 = { В С S \ {ж} : В U {ж} £ 1} ,

а весовая функция является ограничением на S весовой функции для матроида М (в таких случаях говорят, что матроид М получен из М стягиванием (contraction) элемента ж).



[стр.Начало] [стр.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] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]