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

наименьшее экстремальное множество системы матроидов . В терминах орграфа есть множество всех элементов-вершин, достижимых в Гλ из (см. (3.7.2)). Оказыва­ется, в таких же терминах можно описать любое экстремальное

множество системы . Положим

Теорема. где В — произвольная база матроида

Доказательство. По 5.9 Н есть множество всех не λ-активных элементов. Поэтому для ЕслиПо (3.7.2) D = Гλ (). Поэтому если то из 5.2 И наоборот: пусть Тогда по 5.2

и D X. По 5.5 Xi = Bі∩X есть база матроида Мi ∙ X. Поэтому

Х= Гλ (+ (Х|D).

Замечание. Из этой теоремы также непосредственно следует утверждение 5.7.

5.11. Нам понадобится также несколько иное обозначение для графа Гλ, явно указывающее на зависимость Гλ от системы . Пусть Для ЕХ положим

и, как и раньте,

Из 5.10 непосредственно следует

Теорема:

(y1)

(у2) для любого решетка экстремальных

множеств системы матроидов изоморфна решетке

ориентированных разрезов графа (оче-

видно

(у.3) пусть {Ti: i=1, ....., п} — совокупность всех бикомпонент графа Тогда есть совокупность всех join-неразложимых элементов решетки а разбиение {D, Т1, . . ., Tn} есть главное разбиение множества H для решетки

Далее увидим, что для графесть граф

для некоторой другой системы матроидов А и не­которого А-разбиения λА некоторой базы суммы матроидов из A.

5.12. Как и раньше,

Для Х Е положим(так что матроид

Мі * X определен на множество dX),

и

Теорема. Пусть А — экстремальное множество системы

есть -разбиение

базы В матроида

(yl) Ві ∩ А есть база матроида Мі * А, так что есть база матроида

значит, —свободный матроид), λ*А есть

*А — разбиение базы dA;

(у2)

Доказательство:

(д0) Очевидно, Положим

Mj*A=M'j и Bj∩dA=B'j. Достаточно доказать, что для лю­бых

i, j {1, . . ., k}, i≠j и любых

(д1). Докажем сначала следующее вспомогательное утверж­дение. Пусть — множество циклов Т матроида М, таких, что yT и

T∩I Вj (так что Ø≠ Т\Вj D). ТогдаДопустим противное, т. е.Тогда выберем вцикл К с минимальной мощностью множества δК=К\Вj. Пусть zδК. По 5.8 (или по 3.3) есть база Мj · D, значит, существует цикл так что zCzD, следовательно, у Сz. По усиленной аксиоме циклов существует цикл К' матроида М, такой, что

yK'KCz\z. Тогда К'∩IВj, и значит, Но Это противоречит выбору цикла К в

(д2) Предположим,Так как

то из 5.8 следует, что СА, значит, С есть цикл матроида Мj·А. По свойству операции сжатия существует цикл С'у матроида М'j, который содержит у и лежит ва для этого цикла С,