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

3.4. Следствие. В условиях леммы 3.3 X ∩ А есть база си­стемы независимости

3.5. Teopeма. Пусть —последовательность матроидов на множестве Е, M=VMi и β =(X1, . .., Xk) — -разбиение X M и пусть a. Если а не β - активно, то X + а содержит и при том единственный цикл системы незави­симости М, и этот цикл есть А = Гβ(а).

Доказательство. По лемме 3.3 А М. По лемме 3.2 А \ х М для любого х А. Таким образом, А есть единствен­ный цикл системы М в X + а.

3.6. Из леммы 3.2 и теоремы 3.5 вытекает

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

матроидов на множестве Е, β =(X1, . .., Xk)— -разбиение

и a. Тогда если

и только если элемент а β - активен.

Таким образом, если— не максимальное независимое множество в,то его всегда можно увеличить с помощью

активного пути. Доказательство леммы 3.2 фактически содержит алгоритм увеличения множества Х с помощью активного пути. Этот алгоритм перестраивает -разбиение β множества X в но­вое

-разбиение β ' множества X так, чтобы β - активный элемент аХ можно было добавить к некоторому множеству Х'і в β ' и получить по-прежнему независимое множество Х'і + а в М. В качестве активного

β - пути можно выбрать кратчайший актив­ный путь Р = (а = х0, ..., хт) в Гβ. Тогда Р' =(а = х0, ..., хт-1) есть, очевидно, кратчайший активный

путь в новом орграфе Гβ' (см. 3.2). Таким образом, если окрасить элемент хі пути Р в цвет элемента хі+1, i = 0, ..., т — 1, и окрасить элемент хт в цвет р, то для каждого j= 1, .. ., k новое множество цвета j окажется независимым в Mj. Указанный алгоритм увеличения независи­мого множества X виспользуется в алгоритмах решения задач покрытия и упаковки в матpоидах, описанных далее. 3.7. Из теоремы 3.5 вытекает ряд следствий.

3.7.1. Так как из 3.5 для любых и хмножество

X + х имеет не более одного цикла семейства независимости то получаем

Следствие (Нэш-Вильямс). Сумма матроидов есть матроид.

3.7.2. Следствие. Пусть В — база матропдаи

γ= (B1, ..., Bk) есть -разбиение В. Тогда

3.7.3. Следствие. Если С — цикл матроида то

3.7.4.Следствие. Подмножество С из Е есть цикл матрои­да

если и только если для некоторого (а на самом деле, для любого)

с С существует -разбиение γ =(X1, . .., Xk) мно­жества Х = С\с такое, что

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

С = Гγ(с).

3.7.5. Из следствия 3.7.3 получаем

Следствие. СЕ есть цикл матроида

если и только если для каждого элемента сС существует

-разбиение (Х1, .. ., Xk) множества X = С\с такое, что Хi есть база Мi • С, i = l,..., k.

3.8. Очевидно,

для любого XE.

Из леммы 3.3 и следствия 3.7.2 следует, что в указанном выше

неравенстве для

достигается равенство. Таким образом, доказана

Теорема (Нэш-Вильямс).

1.9.4. ПРИМЕНЕНИЕ ТЕОРЕМЫ НЭШ-ВИЛЬЯМС О РАНГЕ СУММЫ МАТРОИДОВ К ЗАДАЧАМ УПАКОВКИ, ПОКРЫТИЯ

И ПЕРЕСЕЧЕНИЯ В МАТРОИДАХ

4.1. Пусть Mi, i = 1, .. ., k,—матроиды на Е и

Очевидно, в Е существует k попарно не пересекающихся баз матроидов М1, ..., Мk, если и только если

а задача отыскания k непересекающихся баз матроидов M1, ..., Мk (ее называют задачей об упаковке баз матроидов M1, ..., Мk в Е) сводится к задаче построения базы суммарного матроида Мk (об алгоритме решения этой задачи см. разд. 8).

4.1.1. Из теоремы Нзш-Вильямса (см. 3.8) вытекает следую­щий критерий существования упаковки баз матроидов M1, ..., Мk в Е.

Теорема. В Е существует набор В1, ..., Bk попарно не пересекающихся баз матроидов М1, . .., Mk соответственно, если и только если для любого Е.

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

Допустим, в Е существует набор В1, ..., Bk попарно не пере­секающихся баз матроидов М1, . . ., Mk, так, что

По теореме Нэш-Вильямса (см. 3.8)

так что

для любого Е. Поскольку тодля любого Е.

Допустим,для любою Е. Тогда

для любого Е, значит, По теореме Нэш-Вильямса (см. 3.7.2) правая часть неравенства равна r(Mk), так что Но очевидно, Таким образом,