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

6.1. Пусть М1, ...., Mk—последовательность матроидов на Е. Обозначим через pack (М1, ...., Mk) задачу отыскания макси­мальной по числу членов последовательности (B1, . . ., Bр) мно­жеств из Е такой, что

Ві ∩ Вj = Ø при i ≠j / и Вi есть база Мi, i=l, .. ., k. Обозначим через

соv (М1, ...., Mk) задачу отыскания минимальной по числу членов последовательности (Х1, .. ., Хс) множеств из Е такой, что Xi есть независимое множество Мi и (если таковая существует). Очевидно, задачи pack (М1, ...., Mk) и cov (М1, ...., Mk) обобщают соответственно за­дачи pack (M) и cov(M) на случай последовательности матрои­дов. Как и в разд. 1.9.4, решение обеих задач сводится к построению баз матроидов

В этом разделе определим для последовательности М1, ...., Mk) матроидов некоторую специальную последовательность (Y1, . . . . . ., Yk) независимых множеств матроидов М1, ...., Mk), называе­мую базовым рядом последовательности (М1, ...., Mk)). Далее увидим, что базовый ряд обладает некоторыми свой­ствами. В частности, он содержит решение как задачи расk(М1, ...., Mk)), так и задачи соv(М1, ...., Mk)). В случае, когда в после­довательности (М1, ...., Mk)) все матроиды одинаковы (Мі = М), а число их k достаточно велико, базовый ряд этой последова­тельности описывает определенные свойства матроида М и на­зывается базовым рядом матроида М. Как отмечалось, прообра­зом понятия базового ряда служит понятие регулярной упаковки стягивающих лесов графа, введенное в 1971 г.

6.2. Рассмотрим последовательность матроидов на Е. Как и в 3.1, последовательность β=(Х1, .. ., Xk) под­множеств из Е назовем -последовательностъю, если

Если то существует -последовательность

β=(Х1, .. ., Xk) такая, что Эту -последовательность β назовем -разбиением X, а -последовательность β =(B1 ,...., Bk) — базовым рядом последовательности матроидов если

(с3)есть база матроида для любого l (1, ..., k).

6.3. Утверждение. Для каждой базы В матроида

существует ее -разбиение, являющееся базовым рядом после­довательности

Доказательство. Пустьи

l = 1, .. ., k. Докажем, что для любой базы Вl матроидаМl су­ществует ее l-разбиение, являющееся базовым рядомl. Для i = 1 утверждение очевидно. Так как то

где Пусть Вk-1 — база матроидасодержащая Хk-1. Тогдагде

Bk = Хk\ Вk-1. Докажем, что Вk-1 — база матроида Допустим

противное, т. е.для некоторого Если

х Bk, то Bk-1 не есть база — противоречие. Если х , то

значит, В не eсть база —противоречие. По предположению индукции существует -разбиение (В1, . .., Bk-1) базы Bk-1, являющееся базовым рядом . Тогда (В1, . .., Bk-1, Вk) есть

-разбиение базы В, являющееся базо­вым рядом .

6.4. Из рассуждений в 6.3 непосредственно следует

Утверждение. Пусть β=(В1, . . ., Bk) — базовый ряд по­следовательности Тогда (|В1|, . .., |Bk|) лексико-графический максимум —_

-последовательность). В частности:

Bl+1 есть база матроида

если β' = ( B'k, . . .,B'k) —базовый ряд , то |Вi|= \|В'i|, i = 1, ...,k.

6.5. Базовый ряд β=(В1, . . ., Bk) матроидов разбивается на блоки следующим образом:

так, что есть

база в Мi и вообще есть база

Обозначим через число блоков базового ряда β. Конечно,зависят от β и и

Число элементов

блока будем называть его длиной. Очевидно,

Из 6.4 следует: если β и β ' — базовые ряды для , то Возможно, для