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

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

Подмножество ХЕ, для которогоестественно назвать препятствием к упаковке баз матроидов М1, ... ..., Mk в Е.

4.1.2. Из теоремы 4.1.1 непосредственно получаем

Следствие. Матроид М на Е имеет k попарно не пересе­кающихся баз, если и только если для любого ХЕ.

4.1.3. Обозначим через pack M максимальное число попарно не пересекающихся баз матроида М. Из 4.1.2 имеем

Следствие.

Задача определения набора В1, ..., Вр из р = pack M попарно не пересекающихся без матроида М в Е сводится, очевидно, к по­следовательности задач упаковки баз М в заданном (все увели­чивающемся) их числе.

4.2. Пусть, как и в 4.1, Мi, i = 1, ..., k,— матроиды на Е и Очевидно, Е есть объединение k независимых множеств

если и только если r (Mk)= |Е|.

Поэтому задача отыскания независимых множеств X1, ..., Хk матроидов M1, ..., Мk, объединение которых есть Е (ее называ­ют задачей о покрытии основного множества Е независимыми множествами матроидов M1, ..., Мk) сводится все к той же за­даче о построении базы суммарного матроида Мk.

4.2.1. Из теоремы Нэш-Вильямса (3.7.2) вытекает

Теорема. Е представило в виде объединения k неза­висимых множеств Хi из Мi, i = 1, . . ., k, если и только если

для любого AЕ.

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

Допустим,

Тогда по теореме Нэш-Вильямса (3.7.2)

так чтодля любого AЕ.

Допустим,

для любого AЕ.Тогда

По теореме Нэш-Вильямса (3.7.2) правая часть неравенства рав­на r(Mk), так что |Е| ≤ r(Mk). С другой стороны, очевидно, |Е| ≥ r(Mk)

>r(Mh). Таким образом, |Е| = r(Mk), значит,

для некоторых XiMi, i = 1, ..., k.

Подмножество XE, для которого естественно назвать препятствием к покрытию множества Е k не­зависимыми множествами матроидов M1,...,Мk. Очевидно, ми­нимальные (по включению) препятствия есть циклы матроида

4.2.2. Из теоремы 4.2.1 получаем

Следствие. Пусть М — матроид на Е. Тогда Е есть объ­единение k независимых множеств матроида М, если и только если для любого A E.

4.2.3. Обозначим через cov M минимальное число независимых множеств матроида М, объединение которых есть Е.

Следствие

Задача о покрытии Е минимальным числом независимых множеств матроида М очевидным образом сводится к последо­вательным задачам о покрытии Е заданным (все возрастающим) числом независимых множеств из М.

4.3. Пусть M1 и М2 — матроиды на Е. Легко видеть, что M1 и М2 имеют общее независимое множество мощности r, если и только если а задача отыскания множества мощности r, независимого как в М1, так и в М2, или выяс~ нения, что такою множества нет (ее называют задачей о пере­сечении матроидов M1 и М2), сводится к задаче о построении ба­зы суммарного матроида М1 + М*2. Задача об отыскании макси­мального множества в Е, независимого как в М1, так и в М2, сводится, очевидно, к задаче о пересечении матроидов.

4.3.1. Из теоремы Нэш-Внльямса (3.7.2) вытекает

Теорема. Пусть М1, М2 — матроиды на Е. Тогда M1 и М2 имеют общее независимое множество мощности r, если и только если для любого АЕ.

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

Допустим,Тогда по теореме Нэш-

Вильямса

значит, так как

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

По теореме Нэш-Вильямса правая часть неравенства равна r(M1 + М*2). Та­ким образом,значит, в Е существует множество мощности r.

1.9.5. ЭКСТРЕМАЛЬНЫЕ МНОЖЕСТВА СИСТЕМЫ МАТРОИДОВ

Пусть Мі — матроид на Е и ρі — ранговая функция Мі, i = 1,...k., ρ — ранговая функция матроида — суммы и

. Множество А, на котором в формуле 3.3 для ранга суммы матроидов достигается минимум правой части

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

Обозначим через класс всех экстремальных множеств системы матроидов Экстремальные множества ес­тественно интерпретировать как «препятствия» на пути построе­ния возможно большего независимого множества (базы) суммы матроидов из Далее убедимся, что есть решетка под­множеств из Е. Более того, в некоторых терминах опишем все экстремальные множества для

5.1. Как отмечалось в 3.8, из 3.4 и 3.7.2 получаем

Утверждение. —экстремалтое множество системы матроидов М.

5.2. Утверждение. ХЕ есть экстремальное множество системыматроидов M1,...,Мk, если и только если

Доказательство. Очевидно, Вместе с тем