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

есть базовый ряд последовательности мат­роидов = (M1, ..., Mk).

Доказательство. Так как есть базы матроидов

соответственно, то В01 + ВХ1 есть база матроида

М1. Положим

Предположим противное, т. е. (В1, . .., Bk) не есть базовый ряд для . Пусть тогда m есть наименьший номер j такой, что множество

Вj не есть база матроида так что j > 1. Докажем, что

m ≤ l. Предположим, что m > l, Тогда Вl — база матроида

и поэтому Но поэтому

По условию есть база матроида

С другой стороны, так как все циклы матроида Мm лежат в А, то есть база свободного матроида

Но тогда

— база матроида Мm - противоречие. Итак, m ≤ l. Пусть — базовый ряд по­следовательности так чтоесть бала Мm.

Положим По 7.2 поэтому

Так как по 7.1

база матроида а ввиду — по условию

— база того же матроида, то Таким образом, — противоречие.

7.6. Теорема. Пусть А — экстремальное множество системы l, l≤k и (B1, .. ., Bk) — базовый ряд последовательности. Тогда есть базовый ряд

последовательности матроидов

Доказательство. Положим По 7.2 Пусть m — наименьший номер такой, что не есть база матронда Легко видеть, что m < l, так как при m ≥ l множествоесть база свободного матронда Пусть есть базовый ряд

последовательности По 7.1 есть базо-

вый ряд для Положим По7.5

есть базовый ряд для m. Поэтому — противоречие.

1.9.8. АЛГОРИТМ ПОСТРОЕНИЯ БАЗОВОГО РЯДА ПОСЛЕДОВАТЕЛЬНОСТИ МАТРОИДОВ

8.1. Рассмотрим последовательность матроидов на Е., Построим базовый ряд для k следующим рекур­сивным способом. Пусть уже построен базовый ряд β'=(Х1, ... ..., Xl) для 1≤ l < k, так что

есть база Мl. Опишем шаг процедуры, который дает базовый ряд для Построим базу Xl+1 матроида Положим

иПостроим граф Гλ. Выясним,

существует ли в Гλ активный путь изЕсли такого пути нет, то по теореме 3.5 λ есть базовый ряд для Если такой путь Р найдется и он начинается с элементато произведем перестройку -последовательности λ с помощью процедуры, описанной в 3.6. В результате перестройки получим новую - последовательность такую, что

х Х'і+1, | X'і | =| Xi | для i = 1, ...,l и | Х'l+1| = |Хl| + 1. Повто­ряя процедуру, получим в конце концов базовый ряд после­довательности . В результате k шагов этой процедуры по­лучим базовый ряд для k.

8.2. Возникает вопрос, какова трудоемкость этого алгоритма. Оракулом независимости матроида М называется такой оракул,

который для каждого предъявленного eму подмножества X Е определяет, является ли X независимым в М (т. е. Х М). Если X есть независимое множество в М (т. е. Х М), то оракул предъявляет некоторый цикл С Х. Будем считать, что каждый матроид Мi задан своим оракулом Оi, а действие алгоритма есть обращение к одному из оракулов Оi. Тогда число действий алго­ритма есть общее число обращений алгоритма к оракулам О1, ... . .., Ok. Очевидно, описанный в 8.1 алгоритм построения базового ряда для k тратит для добавления каждого нового элемента к уже построенной -последовательности не более k ·|Е| обраще­ний к оракулам О1, . . ., Оk (точнее, для построения графа Гλ). Поэтому указанный алгоритм обращается к оракулам О1, . .., Ok не более чем k · |Е|2 раз. Описанный алгоритм строит базовый ряд данного матроида М (а значит, заодно решает за­дачи упаковки и покрытия для М) за