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

Поэтому согласно 3.8 X

— экстремальное множество, если и только если и Последнее означает, что состоит из

одних перешейков матроида

5.3. Из 3.8 и 5.2 получаем

Следствие. — наименьшее экстремальное множество системы матроидов M1,...,Мk.

5.4. Нам понадобится следующее

Утверждение. Для если и только если база матроидаесть объединение непересекающихся матроидов Мі · X, i = 1, ..., k.

Доказательство. Пусть Вi — база Мі · X, i == 1, ..., k,

и Вi∩Вj=Ø для i≠j. Тогда есть база матроида и Обратно: пусть и пусть В есть базаТогда существует -разбиение (Х1, ..., Xk) базы В такое, что

Так как Xi Mi, то для i = 1, ..., k.

Поэтому|Хi| =ρi(Х), значит, Xi—база матроида Mi • X.

5.5. Из 5.2 и 5.4 получаем

Утверждение. ХЕ есть экстремальное множество си­стемы матроидов М1, ..., Mk, если и только если

база матроидаесть объединение непересекающихся баз матроидов М1 ∙ X, .. ., Mk ∙ X;\

5.6. Пусть — класс подмножеств Z E таких, что

(тогда ).

Лемма. Если

Доказательство. Можно считать, что X1 X2 = Е, так как иначе могли бы рассматривать матроиды Мi · (X1 X2) вместо матроидов Мi на Е, i = 1, ..., k. Так как то согласно 5.4 существует упаковка баз матроидов Очевидно, В1i\Х* содержит базу R1i мат­роида Мi×(Х1\Х2). Тогдаесть база Мi · (X1 X2), значит, (В1, ..., Bk) — упаковка баз матроидов M1, . .., Mk. Со­гласно 5.4

5.7. Из леммы 5.6 следует, что в классе существует наибольшее (по включению) множество, которое обозначим че­рез . Из 5.1 Поэтому из 5.2 вытекает

Теорема есть решетка подмножеств из Е (по включению), причем есть наибольшее множество, а

наименьшее множество решетки множеств

5.8. Лемма. Пусть 1 = (Ви ..., Вк) есть -разбиение базы В матроидаи X — некоторое экстремальное множество си­стемы М1, .. ., Мk. Тогда Вi ∩ X есть база Мi • X, i = 1, ..., k.

Доказательство. Положим Xi = Вi ∩ X. По 5.2

Поэтому есть база

так что По 5.2

Так как для любого i = 1, ..., k Хi Мi значит, |Хi|≤ρi(Х), для любого i = 1, ..., k Хi Мi , есть база Мi • X.

5.9. Пусть λ = (B1, ..., Вk) есть -разбиение базы В матроида а К (λ) обозначает множество всех не λ -активных элемен­тов (вершин в Гλ).

Теорема. (так что не зависит ни от λ, ни от В).

Доказательство. Пусть По 5.8 Н ∩ Вi есть база

Мi • Н, поэтому каждый из Н не λ-активен, значит, Н К(λ).

Остается доказать, что Так как

то согласно 5.5 достаточно доказать, что

Кі (λ) = Ві∩К(λ) есть база матроида М'і = Мі•К (λ). Рассмотрим

хК(λ)\Кі(λ) и докажем, что Кі(λ)+ х Мі. Так как х — не λ - активен, существует цикл С(Мі, Ві + х). Если этот цикл содержит элемент у из Bі\Kі(λ), то у есть λ - активный элемент, а значит, х — тоже λ-актнвпый элемент — противоречие. Таким образом, D

5.10. Пусть, как и раньше, λ = (Ві, . . ., Вk) есть -разбиение базы В матроидаВ 5.7 мы убедились, что есть