Дискретно-непрерывная математика (стр. 27 )

находим активный λ - путь, точнее, чередующийся λ - путь вида

, где

i=1, . .., r и X + у М. С помощью этого активного λ-пути Р производим перестройку -последовательности λ в новую

-послоловательность ' такую, что есть новый -ряд, Очевидно, βk+1 есть результат λ р некоторой итерации Tk+1, p.

8.5. Оценим число обращений к оракулу независимости в опи­санном в 8.4 алгоритме построения базового ряда матроида М.

Пусть в результате работы алгоритма построен базовый ряд

(К1, .. ., Кс) матроида М, где с = cov M. Оценим число pk+1, r+1 обращений на итерации Tk+1, r+1. Для построения базы X матроида M\Br(k), содержащего Вrk+1, а также для создания X1 и спи­ска циклов требуется обра­щений к оракулу. Для построения Xl, Yl+1, Гl и Гl+1, где l требуется

обра­щений. Так как |Х| ≤ |Kk+1|, то шаг Tk+1 имеет не более |Kk+1|+ 1 итераций. Поэтому для числа pk+1 обращений на шаге Tk+1 имеем

Тогда для числа р обращений всего алгоритма к оракулу получим

Очевидно,

Легко видеть: еслито

Поэтому

1.9.9. СРАВНЕНИЕ РАЗЛИЧНЫХ АЛГОРИТМОВ УПАКОВКИ, ПОКРЫТИЯ И ПЕРЕСЕЧЕНИЯ В МАТРОИДАХ

Как отмечалось в разд. 1.9.4, всякий алгоритм для задачи упа­ковки, покрытия или пересечения в матроидах строит фактиче­ски базу суммы некоторых матроидов. Вместе с тем любой алго­ритм построения базы суммы матроидов, останавливаясь, «упира­ется» в некоторое «препятствие», являющееся экстремальным множеством системы матроидов-слагаемых. Как показано в 1.9.5, набор экстремальных множеств для системы матроидов образует решетку (по включению). Оказыва­ется, любой пз известных алгоритмов построения базы суммы наталкивается на препятствие, представляющее собой либо

максимальное, либо минимальное экстремальное множество в ре-шотке , так что все известные алгоритмы можно расклас-

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

9.1. Алгоритм Эдмондса разбиения множества Е на минималь­ное число независимых множеств матроида. Если М имеет петли, то задача, очевидно, не имеет решения. Поэтому будем считать, что М не имеет петель. Пусть Мі=М, і= 1, 2, ...,— матроид на и

Предположим, подмножество ХЕ разбивается минимумна k независимых мно­жеств матроида М и построено некоторое такое разбиение (Х1, .... .., Хk) (так что =X).

Цель очередного шага алгоритма состоит в выяснении, существует ли хЕ\Х такой, что Если да, то множество X' тоже разбивается минимум на k независимых множеств из М и алгоритм строит некоторое такое разбиение (Х1, ...,Xk) (так что ' =X' ).

В противном случае k заменяется на k + 1, а именно: для X' = X + х, где X'k+1)

есть минимальное -разбиение. Затем, если X' ≠ Е, то этот шаг повторяется исходя из получившегося минималь­ного разбиения нового множества X'.

Опишем теперь шаг алгоритма, который исходит из мини­мального разбиения (Х1, .. ., Хk) множества Строим

последовательность Т0, Т1, . . ., Тр замкнутых в М множеств,

для некоторого si такого, что Последний номер р определяется первым

моментом, когда либо (al) для любого

i {0, . . ., р}, либо (а2) Легко видеть, что

Т0 T1 .. . Тр и что такой момент р существует. В случае (al)

и по теореме 5.9 X есть база матроида

Мk, а Тр есть экстремальное множество системы матроидов . В случае (а2) X + x Мk для любого и - раз-

биение множества Х+ х={Х1, ..., Xk) строится некоторым об­разом с помощью последовательности Т0, Т1, . . ., Тр.

Утверждение. Если шаг алгоритма Эдмондса заканчива­ется случаем (al), то Тр есть наибольшее множество Н(Мk) решетки экстремальных множеств системы

Доказательство. Заметим вначале, что так как X есть база матроида Мk , а то X ∩ Н(Мk) есть база матроида

Мk ∙ Н(Мk), поэтому согласно 5.8 есть база матроида Мі • Н(Мk), і = 1, ..., k. Покажем, что H(Мk) Ti, i = 0, .. ., р индукцией по i. Очевидно, Н(Мk)=E=Т0. Предпо­ложим, Тогда для любого

i = 1.....k. Кроме того, Н(Мk) = d (X'i). Так как