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

Предположим, все Аi из есть системы независимости. Тог­да, очевидно, А есть также система независимости. Для такого по каждой -последовательности λ=(Х1, . . ., Xk) построим граф следующим образом: VГλ = Е и для х, у E (х, у) есть дуга в Гλ, если и только если

для некоторого i {1, . .., k} х Хi, а у Хi;

y принадлежит некоторому циклу системы независимости Аi, лежащему Xi + x

Путь в графебудем называть λ - путем. λ - путь назовем

активным или увеличивающим путем, если найдется Xi из λ та­кое, что последний элемент х этого пути не принадлежит Xi и Xi + х Аi. Элемент ж из E назовем λ - активным, если x при­надлежит некоторому λ - активному пути.

При рассмотрении фиксированного -разбиения λ = (X1, .. . . .., Xk) множества X удобно считать, что элементы множества Хi окрашены в цвет i, а элементы из Е \ X не окрашены. Тогда процесс перестройки -разбиения λ можно интерпретировать как процесс перекраски и окраски элементов из Е.

1.9.3. ПОНЯТИЕ УВЕЛИЧИВАЮЩЕГО ПУТИ И КОНСТРУКТИВНОЕ ОПИСАНИЕ ЦИКЛА СУММЫ МАТРОИДОВ

Важную роль в теории матроидов играет понятие суммы матроидов. Оно оказывается весьма существенным для задач максимальной упаковки баз матроидов, минимального покрытия исходного множества Е базами (или независимыми множествами) матроида, а также отыскания максимального не­зависимого множества двух матроидов на одном и том же мно­жестве Е. В настоящем разделе дано понятие увеличивающего или активного пути, интересного тем, что с его помощью всегда можно увеличить независимое множество сум­мы матроидов, если оно не максимально. Приведено конструк­тивное описание цикла суммы матроидов, которое существенно иcпользуется в дальнейшем. С помощью этого описания цикла суммы матроидов даны простые доказательства теорем Нэш-Вильямса о сумме матроидов.

3.1. Пусть есть последовательность матро­идов на множестве Е и λ =(Х1, . . ., Xk есть некоторая -после­довательность (см. 2.3). λ-путь Р = (х0, . . ., хт) назовем актив­ным (или увеличивающим) путем, если найдется Xі λ такое, что хт Хі и Xi + хт Мі. Элемент х из Е назовем λ -активным, если х принадлежит некоторому λ - активному пути. Далее всюду ρі есть ранговая функция матроида Мі.

3.2. Лемма. Пусть .....— последовательность

матроидов на множестве Е, λ = (Х1, ..., Xk) есть -разбиение

множества X из Если элемент zE\X λ - активен,

то X + z M.

Доказательство. Пусть P= (z = x0, х1 . . ., хт)-актив­ный λ - путь,

xk Xik, k = 1, . . ., т, так что хт + ХрМр для некоторого

р {1, . . ., k }, р = im. Если т=0, то Хр+zМр, значит, Предположим, лемма верна для активных λ-путей длины меньше т. Покажем, что она верна также для активного λ-пути длины т. Построим новое

-разбиение множества X, положив Хі = X

дчя і ≠ im, р и Предположим,

Р* = (z = х0, . . ., хm-1) есть λ '-путь. Так как

то Р* есть активный λ'-путь длины т — 1, зна­чит, по предположению индукции X + zM. Предположим те­перь, что Р* не есть λ '-путь. Пусть тогда с — наименьший номер, для которого дуга (хс, хс+1) пути Р не есть λ '-дуга, так что Р' =(z = х0, ..., хс) есть λ '-путь. Очевидно, (хс, xc+1) не есть λ'-дуга, если и только если

Поэтому , значит, Р' есть актив-

ный λ '-путь длины с ≤ т — 1. По предположению индукции

X + zM.

3.3. Лемма. Пусть — последовательность матроидов на Е, β = (X1, ..., Xk) — λ -разбиение множества

X VMі. Предположим, элементы множества Y X не β - актив­ны. Положим А = Г (Y). Тогда Х'i == Хi ∩ А есть база матроида

М'i =Mi∙A, i = l, ...k.

Доказательство. Предположим, Хі + х Mi для неко­торого i1, .. ., k} и х β А \ X. Так как х А, то существует β - путь Р из некоторого

у Y в х. Так как Хi + х Мi, то β - путь Р активен, значит,

у — β - активный элемент в Y — противоречие. Поэтому х + Хi Mi для любых i {1, . . ., k} и х А \ Хi. Тогда

так что Х'i +х Mi, следовательно, Х'i есть база в М'i.