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

т. е. lj( β, ), вообще говоря, зависит от β.

6.6. Рассмотрим последовательность из k

одинаковых матроидов M, и нусть βk =(B1, . . ., Вk) есть базовый ряд Тогда, очевидно, Вi=Ø при i=с=covM. Базовый ряд последовательности из с = cov М одинаковых матроидов М

будем называть базовым рядом матроида М. Легко видеть, что

каждый блок базового ряда β матроида М состоит из множеств одинаковой мощности: ._

число ri( β, M) назовем рангом блока

число блоков, длина и ранг каждого блока базового ряда β матроида М не зависят от β, а зависят только от М:

Очевидно,

Таким образом, базовый ряд матроида М есть разбиение Е на ми­нимальное число независимых множеств матроида М, причем это разбиение состоит из серии максимальных упаковок баз «сужа­ющихся» матроидов.

1.9.7. БАЗОВЫЙ РЯД И ЭКСТРЕМАЛЬНЫЕ МНОЖЕСТВА ПОСЛЕДОВАТЕЛЬНОСТИ МАТРОИДОВ

7.1. Пусть , где М1 — матроид на Е.

Пусть АЕ . Если λ = (Х1, . .., Хk), то положим

Последовательность множеств λ • A будем называть следом последовательности множеств λ на А. Положим

и Если

β =( B1, . . ., Bk) — базовый ряд последовательности матроидов , то след β•A базового ряда β на А не есть, вообще говоря, базо­вый ряд последовательности матроидов ∙А. Однако если А — экстремальное множество системы то дело обстоит иначе.

Теорема. Пусть β есть базовый ряд последовательности матроидов и ∙А есть экстремальное множество последователь­ности матроидов Тогда β•А есть базовый ряд после­довательности матроидов ∙А.

Доказательство. По определению базового ряда для каж­дого j = 1, ...,k множество есть база матроидаСогласно 5.2 припоэтому

есть база матроида Со-

гласно 5.5 база есть объединение непересекающихся

баз матроидов M1∙А, ..., Ml∙А соответственно. Поэтому и при i< l множествоесть база матроида

Следствие. Пусть Мi = М и А — экстремальное множество последовательности матроидов Тогда если

β есть базовый ряд матроида М, то β•А есть базовый ряд мат­роида М ∙ А.

7.2.Утверждение. Пусть А—экстремальное множество для, a (B1, ... ., Вk) есть базовый ряд для Mk; l≤k. Тогда

Доказательство. Так то

при i = l+1, .. ., k. Предположим противное, т. е. для некото­рого i ≤ l множество содержит цикл С' матроида По определению сжатия существует цикл С матроида Mi такой, что Среди таких циклов выберем цикл С с мини­мальной мощностью множества С\Вi. Так как С Вi, то С\Вi ≠Ø. Пз 5.5 следует, что Вi∩А есть база матроида Mі∙A. По­этому для каждого элемента хС\Ві существует цикл С (Мі, Ві + х) А. Фиксируем хС\Ві, уС'. По усиленной аксиоме циклов существует цикл С" матроида М такой, что Так как то С"∩= С'. Но что противоречит выбору цикла С.

7.3. Следствие. Пусть А — экстремальное множество для Тогда матроид

свободный.

Доказательство. Положим в утверждении 7.2 l=k. Тог­да

а

7.4. Следствие. Пусть Mi = M. Тогда экстремальное мно­жество системы матроидов замкнуто в матроиде М.

Доказательство. Пусть (В1, .. ., Вс), где c = covM. есть базовый ряд матроида М. По 7.2

Но поэтому в нет петель матроида

М, т. е. c1(A) = A.

Замечание. Если система матроидов состоит не из

одинаковых матроидов, то экстремальное множество А системы может, вообще говоря, не быть замкнутым в каждом матроиде Мі.

7.5. Теорема. Пусть А — экстремальное множество систе­мы, а есть базовые ря­ды последовательностей матроидов и

соответственно. Тогда