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

(cov M) · |Е|2 обращений к оракулу независимости О(М), описывающему М. Так как cov M не более (и может быть порядка) |Е|, то указанный алго­ритм требует, вообще говоря, О(|Е|3) обращений к оракулу независимости (или, как будем говорить, проверок независимо­сти) . Все известные алгоритмы решения задач упаковки и по­крытия требуют того же числа O(|Е|3) проверок независимости. Далее приведем модификацию указанного алгоритма, кото­рая требует рекордно маленького числа O(|Е|3) проверок неза­висимости для построения базового ряда данного матроида. Прообразом этого алгоритма служит алгоритм по­строения регулярной упаковки в графах.

8.3. Для уменьшения трудоемкости описанного выше алго­ритма важна следующая лемма о «вилке».

Л е м м а. Пусть и Вк — база в Мk, а именно:

а Х— база матроида M\Bk и λ=(B1, .. ., Вk, X). Тогда для любой дуги (у, z) в Гλ; у, zX, существует «вилка» из двух дуг (у, х) и (х, z) схX.

Доказательство. Пусть zBi. Так как (у, z) —дуга в Гλ, то существует, и притом единственный, цикл Сyz = С (М, В+у) такой, что z Сyz. Поскольку X — база в M\Bk, то X + у содержит, и притом единственный, цикл С = С(М, X + у). Так как Bk — база Mk, для любого а E\Bk существует единственный цикл Са = С (М, В + а). Требуется доказать, что для некоторого х С ∩ X = С\у в Гλ существует дуга

(х, z), т. е. существует цикл Сх такой, что z Сх. Допустим противное. Рассмотрим цикл Сх, х С\у. По усиленной аксиоме цикловв М существует цикл А такой, что у A С Сх\х, поэтому yAC Bi\z. Пусть А = {А : yAC Bi\z }, и пусть и Если С* ∩ X = Ø, то

С*Вi+ у, зна­чит, С* = Суz. Но z Cyz\C* — противоречие. Таким образом, По усиленной аксиоме циклов существует цикл С' такой, что следовательно, yC' Bi. Так как по предположению то значит, Но а отсюда

Это противоречит выбору С*.

8.4. Опишем теперь модификацию алгоритма в 8.1, которая строит базовый ряд одного матроида М на Е, но требует мень­шего числа проверок независимости. Пусть, как и в 8.3,

, по теперь

Mi = M, t = 1, . . ., с и с = cov M. Как и в 8.1, алгоритм по­строения базового ряда рекурсивный. Он состоит из с шагов Т1, . . ., Тс. На шаге Tk строится базовый ряд βk для k. В ча­стности, на шаге Т1 строится база В матроида М и β1 = {B}. Опи­шем шаг Tk+1, k≥ 1, который следует после выполнения шага Tk, так что к началу шага Tk+1 имеем k - ряд βk= (В1, ... ...,Вk). Шаг Tk+1 состоит из последовательных итерации Tk+1, r. На ите­рации Tk+1, r строится -последовательность

λr =(Вr1, ... ...,Вrk+1) такая, что (Вr1, ... ...,Вrk) есть k -ряд . Итерация Tk+1,0 тривиальна, eе результат —-последовательность

Опишем итерацию Tk+1, r+1, r ≥0, которая следует после Tk+1, r, так что к началу итерации Tk+1, r+1 имеем -последовательность

Положим Вначале строим

базу X матроида М\Вr(k), содержащую Вrk+1, а также список

циклов Положим

λ= (Вr1, ..., Вrk+1, Х). Очевидно, |Х|≤| Вrk |. Если X = Е\Вr (k) или |Х|=| Вrk |, то βk+1= λ. Предположим, и |Х|<|Вrk|. Положим , так что Х1 есть множество всех циклических элементов матроида М\Вr(k), ле­жащих в X. Рекуррентно определяем множества Yi+1=Гλ(Xi) и Обозначим через Гi и Гi+1 множества дуг в Гλ, ведущих из Хi в Yi+1 и из Yi+1 в Хi+1 соответственно. Пусть l = l(l + 1, r + 1) — минимальное s такое, что

(cl) Xs+1 = Xs, а значит, Ys+1 = Ys;

либо (с2) в Xs+1 есть элемент у такой, что X + y М.

В случае (cl) βk+1 = λ, при этом

В случае (с2), пользуясь множествами Гl, Гl+1 и