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

существует цикл Су матроида Мj·А такой, чтоТогда

у Су. Предположим, хС'у. Тогда Су ∩IВj , значит, Су Это противоречит (д1). Таким образом, х, у С'у. Так как С'у С, то

(д3) Предположим теперь наоборот, что Рассмотрим также цикл С=С(Мj, Вj + х). Пусть уС. Как отмечалось в (д1), СA. По свойству сжатия существует цикл Сxy матроида М такой, что По усиленной аксиоме циклов (примененной к циклам С и Сxy) существует цикл Су такой, что Тогда Су∩IВj значит, Это противоречит (д1). Таким образом, справедливо

5.13. Утверждение. Если матроид свободный (т. е. , то

Доказательство (индукцией по k). Для k=1 утвержде­ние непосредственно следует из свойств операции сжатия. Пусть утверждение верно для k = р ≥ 1; докажем eго для k = р + 1.

ПоложимПредположим, что существует

элемент х А ∩ D(M1М2). По свойству операции сжатия су­ществует цикл С матроида (M1М2) × А и цикл С* матроида М1 М1 такие, что х С* = С* ∩ А. Согласно конструкции цикла суммы матроидов (см. 3.5) С*\х = X1 + X2, где Хі — база мат­роида Мі ∙ С*, i = l, 2. Положим Хі1 = Хі ∩ А.Возможны случаи:

(cl) Х1 = Х2 = Ø;

(с2) одно из множеств X1, X2, скажем Х1, пусто, а другое, т. е. X2 не пусто;

(с3) оба множества X1 и X2 но пусты.

В случае (cl) х есть петля матроида=, что противоречит условию утверждения. В случае (с2) х есть петля матроида М1 × А и каждый элемент у из Х21 — тоже петля матроида М1 × А, так как Таким

образом, множество Х21 +х состоит из одних нетель матроида М1 × А. Так как М1 × А + М2 × А — по условию свободный матроид, то А — его база, значит, Так как

Х21 + х состоит из петель матроида М1 × А, то Х21 +х М2 × А. Согласно конструкции цикла суммы матроидов в 3.5 существует элемент z X1 + х такой, что и по свойству операции сжатия должен существовать цикл мат­роида М2 × А, лежащий в Х21+ х, значит,— про­тиворечие.

Таким образом, остается исследовать случай (с3). Пусть

Хі2 Хі1 — база минора Тогда

Докажем, что Хі2— база минора (Мі × А) ∙ С,

і=1, 2, т. е. что для каждого элемента у С\Хі2 существует цикл Так как Хі — база матроида Мі • С*, то X'+ у содержит цикл С(Мі, Хі + у). Возможны два случая:

В случае (с3.1) у есть петля в Мі×А, значит, она есть иско­мый цикл В случае (с3.2) по свойствам опе­рации сжатия найдется цикл С' матроида Мі×А такой, что уС', С'\у Хі2. Покажем, что существует цикл Предположим, что цикл С' выбран так, что мощность множества С'\Хі2 минимальна. Если существует элемент zС'\Хі2, z≠y, то zХ Хі1 и существует цикл. Тогда по усилен­ной аксиоме циклов существует цикл С" матроида Мі×А такой, что Цикл С" обладает теми же свойствами, что и С', но — это про­тиворечит выбору цикла С'. Следовательно, С'\Хі2= {у}, т. е.

Таким образом, в случае (с3) множество

есть база матроида поэтому суще­ствует циклчто противоречит усло­вию утверждения.

5.14. Теорема. Подмножество ХЕ есть экстремальное

множество матроида тогда и только тогда, когда

и матпроидсвободный.

Доказательство. Необходимость следует из утвержде­ний 5.2 и 7.3, достаточность — из утверждений 5.2 и 5.13.

5.15. Утверждение. Пусть ХЕ таково, что

г Тогда матроид свободный, если и только только если

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